1. |
- Björklund, Johanna, et al.
(författare)
-
Z-Automata for Compact and Direct Representation of Unranked Tree Languages
- 2019
-
Ingår i: Implementation and Application of Automata. - Cham : Springer. - 9783030236786 - 9783030236793 ; , s. 83-94
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|