Skip to content
Show report in:

UMINF 18.17

Z-automata for Compact and Direct Representation of Unranked Tree Languages

Unranked tree languages are valuable for modelling structured objects such as XML documents, database entries, and dependency trees. We introduce a new type of automaton for unranked tree languages, called Z-automaton. The model is closely related to stepwise tree automata, thus offering a compact form of representation, but it avoids obfuscating encoding schemes. We discuss alternative semantics and normal forms, and finally prove the membership problem to be in O(mn), where m is the size of the transition table, an n is the size of the input tree.


Unranked trees, Automata, Complexity, Efficiency


Johanna Björklund , Frank Drewes and Giorgio Satta

Back Edit this report
Entry responsible: Johanna Bjorklund

Page Responsible: Frank Drewes