Sökning: onr:"swepub:oai:DiVA.org:umu-158624" >
Z-Automata for Comp...
Z-Automata for Compact and Direct Representation of Unranked Tree Languages
-
- Björklund, Johanna (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
- Drewes, Frank (författare)
- Umeå universitet,Institutionen för datavetenskap,Foundations of Language Processing
-
- Satta, Giorgio (författare)
- University of Padova, Italy
-
(creator_code:org_t)
- 2019-06-26
- 2019
- Engelska.
-
Ingår i: Implementation and Application of Automata. - Cham : Springer. - 9783030236786 - 9783030236793 ; , s. 83-94
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Unranked tree languages are valuable in natural language processing for modelling dependency trees. We introduce a new type of automaton for unranked tree languages, called Z-automaton, that is tailored for this particular application. The Z-automaton offers a compact form of representation, and unlike the closely related notion of stepwise automata, does not require a binary encoding of its input. We establish an arc-factored normal form, and prove the membership problem of Z-automata in normal form to be in O(mn), where m is the size of the transition table of the Z-automaton and n is the size of the input tree.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Computer Science
- datalogi
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas