Abstract
We introduce tree stack automata as a new class of automata with storage and identify a restricted form of tree stack automata that recognises exactly the multiple context-free languages.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
The control flow of our constructed automaton is similar to that of the treewalk evaluator for attribute grammars [8, Sect. 3]. The two major differences are that the treewalk evaluator also treats inherited attributes (which are not present in PMCFGs) and that our constructed automaton generates the tree on the fly (while the treewalk evaluator is already provided with the tree).
- 2.
The k-MCFG \(G({\mathcal {M}})\) exists since \([\![\cdot ]\!]\) is a homomorphism and k-MCFLs are closed under homomorphisms [13, Theorem 3.9].
References
Aho, A.V.: Nested stack automata. JACM 16(3), 383–406 (1969)
Chomsky, N.: Formal properties of grammars. In: Luce, R.D., Bush, R.R., Galanter, E. (eds.) Handbook of Mathematical Psychology, vol. 2. Wiley, New York (1962)
Villemonte de la Clergerie, É.: Parsing MCS languages with thread automata. In: Proceedings of TAG+02, pp. 101–108 (2002)
Villemonte de la Clergerie, É.: Parsing mildly context-sensitive languages with thread automata. In: Proceedings of COLING 2002, vol. 1, pp. 1–7. ACL (2002)
Engelfriet, J.: Context-free grammars with storage. CoRR (2014)
Guessarian, I.: Pushdown tree automata. Math. Syst. Theor. 16(1), 237–263 (1983)
Herrmann, L., Vogler, H.: A Chomsky-Schützenberger theorem for weighted automata with storage. In: Maletti, A. (ed.) CAI 2015. LNCS, vol. 9270, pp. 115–127. Springer, Heidelberg (2015). doi:10.1007/978-3-319-23021-4_11
Kennedy, K., Warren, S.K.: Automatic generation of efficient evaluators for attribute grammars. In: Proceedings of POPL 1976 (1976)
Kuhlmann, M., Satta, G.: Treebank grammar techniques for non-projective dependency parsing. In: Proceedings of EACL 2009, pp. 478–486. ACL (2009)
Maier, W.: Direct parsing of discontinuous constituents in German. In: Proceedings of SPMRL 2010, pp. 58–66. ACL (2010)
Schützenberger, M.P.: On context-free languages and push-down automata. Inf. Control 6(3), 246–264 (1963)
Scott, D.: Some definitional suggestions for automata theory. J. Comput. Syst. Sci. 1(2), 187–212 (1967)
Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. TCS 88(2), 191–229 (1991)
Vijay-Shanker, K.: A study of tree adjoining grammars. Ph.D. thesis (1988)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Denkinger, T. (2016). An Automata Characterisation for Multiple Context-Free Languages. In: Brlek, S., Reutenauer, C. (eds) Developments in Language Theory. DLT 2016. Lecture Notes in Computer Science(), vol 9840. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53132-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-662-53132-7_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-53131-0
Online ISBN: 978-3-662-53132-7
eBook Packages: Computer ScienceComputer Science (R0)