Abstract
In this paper we introduce a sub-family of synchronized alternating pushdown automata, Deterministic Synchronized Alternating Pushdown Automata, and a sub-family of conjunctive grammars, LR(0) Conjunctive Grammars. We prove that deterministic SAPDA and LR(0) conjunctive grammars have the same recognition/generation power, analogously to the classical equivalence between acceptance by empty stack of deterministic PDA and LR(0) grammars. These models form the theoretical basis for efficient, linear, parsing of a rich sub-family of conjunctive languages, which properly includes all the boolean combinations of context-free LR(0) languages.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aizikowitz, T., Kaminski, M.: Conjunctive grammars and alternating pushdown automata. In: Hodges, W., de Queiroz, R. (eds.) Logic, Language, Information and Computation. LNCS (LNAI), vol. 5110, pp. 30–41. Springer, Heidelberg (2008)
Aizikowitz, T.: Synchronized Alternating Pushdown Automata. PhD thesis, Technion – Israel Institute of Technology (2010), http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2010/PHD/PHD-2010-14
Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. Journal of the ACM 28(1), 114–133 (1981)
Higginbotham, J.: English is not a context-free language. Linguistic Inquiry 15, 119–126 (1984)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)
Knuth, D.E.: On the translation of languages from left to right. Information and Control 8, 607–639 (1965)
Ladner, R.E., Lipton, R.J., Stockmeyer, L.J.: Alternating pushdown and stack automata. SIAM Journal on Computing 13(1), 135–155 (1984)
Langendoen, T.D., Postal, P.M.: English and the class of context-free languages. Computational Linguistics 10(3-4), 177–181 (1984)
Okhotin, A.: Conjunctive grammars. Journal of Automata, Languages and Combinatorics 6(4), 519–535 (2001)
Okhotin, A.: Top-down parsing of conjunctive languages. Grammars 5(1), 21–40 (2002)
Okhotin, A.: LR parsing for conjunctive grammars. Grammars 5(2), 21–40 (2002)
Okhotin, A.: A recognition and parsing algorithm for arbitrary conjunctive grammars. Theoretical Computer Science 302, 81–124 (2003)
Okhotin, A.: Fast parsing for boolean grammars: A generalization of valiant”s algorithm. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol. 6224, pp. 340–351. Springer, Heidelberg (2010)
Tomita, M.: Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Kluwer Academic Publishers, Norwell (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aizikowitz, T., Kaminski, M. (2011). LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata. In: Kulikov, A., Vereshchagin, N. (eds) Computer Science – Theory and Applications. CSR 2011. Lecture Notes in Computer Science, vol 6651. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20712-9_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-20712-9_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20711-2
Online ISBN: 978-3-642-20712-9
eBook Packages: Computer ScienceComputer Science (R0)