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 \left( mn \right) \), where m is the size of the transition table of the Z-automaton and n is the size of the input tree.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Brüggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets: version 1. Techcial report HKUST-TCSC-2001-0, The Hong Kong University of Science and Technology (2001). http://repository.ust.hk/ir/Record/1783.1-738
Carme, J., Niehren, J., Tommasi, M.: Querying unranked trees with stepwise tree automata. In: van Oostrom, V. (ed.) RTA 2004. LNCS, vol. 3091, pp. 105–118. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-25979-4_8
Comon, H., et al.: Tree automata techniques and applications. http://www.grappa.univ-lille3.fr/tata. Accessed 12 Oct 2007
Droste, M., Vogler, H.: Weighted logics for unranked tree automata. Theory Comput. Syst. 48(1), 23–47 (2011). https://doi.org/10.1007/s00224-009-9224-4
Gécseg, F., Steinby, M.: Tree Automata. Akadémiai Kiadó, Budapest (1984). https://arxiv.org/abs/1509.06233
Högberg, J., Maletti, A., May, J.: Backward and forward bisimulation minimization of tree automata. Theor. Comput. Sci. 410(37), 3539–3552 (2009). https://doi.org/10.1016/j.tcs.2009.03.022. Preliminary version. In: CIAA 2007
Kübler, S., McDonald, R., Nivre, J.: Dependency Parsing. Morgan and Claypool Publishers, New York (2009). https://doi.org/10.2200/S00169ED1V01Y200901HLT002
Libkin, L.: Logics for unranked trees: an overview. Log. Methods Comput. Sci. 2(3), 1–31 (2006). https://doi.org/10.2168/LMCS-2(3:2)2006
Maletti, A., Graehl, J., Hopkins, M., Knight, K.: The power of extended top-down tree transducers. SIAM J. Comput. 39(2), 410–430 (2009). https://doi.org/10.1137/070699160
Martens, W., Niehren, J.: Minimizing tree automata for unranked trees. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 232–246. Springer, Heidelberg (2005). https://doi.org/10.1007/11601524_15
Martens, W., Niehren, J.: On the minimization of XML schemas and tree automata for unranked trees. J. Comput. System Sci. 73(4), 550–583 (2007). https://doi.org/10.1016/j.jcss.2006.10.021
Acknowledgment
We thank the reviewers for carefully reading the manuscript. In particular, we thank one reviewer who pointed out a flaw in the original version of Theorem 1.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Björklund, J., Drewes, F., Satta, G. (2019). Z-Automata for Compact and Direct Representation of Unranked Tree Languages. In: Hospodár, M., Jirásková, G. (eds) Implementation and Application of Automata. CIAA 2019. Lecture Notes in Computer Science(), vol 11601. Springer, Cham. https://doi.org/10.1007/978-3-030-23679-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-23679-3_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-23678-6
Online ISBN: 978-3-030-23679-3
eBook Packages: Computer ScienceComputer Science (R0)