Sökning: onr:"swepub:oai:DiVA.org:umu-182984" >
Faster Computation ...
Faster Computation of N-Best Lists for Weighted Tree Automata
-
- Björklund, Johanna, 1961- (författare)
- Umeå universitet,Institutionen för datavetenskap
-
- Drewes, Frank (författare)
- Umeå universitet,Institutionen för datavetenskap
-
- Jonsson, Anna (författare)
- Umeå universitet,Institutionen för datavetenskap
-
(creator_code:org_t)
- Engelska.
- Relaterad länk:
-
https://urn.kb.se/re...
Abstract
Ämnesord
Stäng
- We show that a previously proposed algorithm for the N-best trees problem – not to be confused with the easier N-best runs problem – can be made more efficient by changing how it arranges and explores the search space. Given an integer N and a weighted tree automaton (wta) M over the tropical semiring, the algorithm computes N trees of minimal weight with respect to M. Compared to the original algorithm, the modifications increase the laziness of the evaluation strategy, which makes the new algorithm asymptotically more efficient than its predecessor.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- N-best lists
- weighted tree automata
- tropical semiring
Publikations- och innehållstyp
- vet (ämneskategori)
- ovr (ämneskategori)