Abstract
The paper considers a family of formal grammars that extends linear context-free grammars with an operator for referring to the left context of a substring being defined, as well as with a conjunction operation (as in linear conjunctive grammars). These grammars are proved to be computationally equivalent to an extension of one-way real-time cellular automata with an extra data channel. The main result is the undecidability of the emptiness problem for grammars restricted to a one-symbol alphabet, which is proved by simulating a Turing machine by a cellular automaton with feedback. The same construction proves the \(\Sigma^0_2\)-completeness of the finiteness problem for these grammars.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aizikowitz, T., Kaminski, M.: LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol. 6651, pp. 345–358. Springer, Heidelberg (2011)
Barash, M.: Recursive descent parsing for grammars with contexts. In: SOFSEM 2013 Student Research Forum (2013)
Barash, M., Okhotin, A.: Defining contexts in context-free grammars. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 106–118. Springer, Heidelberg (2012)
Barash, M., Okhotin, A.: An extension of context-free grammars with one-sided context specifications (September 2013) (submitted)
Čulík II, K., Gruska, J., Salomaa, A.: Systolic trellis automata. International Journal of Computer Mathematics 15, 195–212, 16, 3–22 (1984)
Dyer, C.: One-way bounded cellular automata. Information and Control 44, 261–281 (1980)
Ibarra, O.H., Kim, S.M.: Characterizations and computational complexity of systolic trellis automata. Theoretical Computer Science 29, 123–153 (1984)
Jeż, A.: Conjunctive grammars can generate non-regular unary languages. International Journal of Foundations of Computer Science 19(3), 597–615 (2008)
Jeż, A., Okhotin, A.: Conjunctive grammars over a unary alphabet: undecidability and unbounded growth. Theory of Computing Systems 46(1), 27–58 (2010)
Jeż, A., Okhotin, A.: Complexity of equations over sets of natural numbers. Theory of Computing Systems 48(2), 319–342 (2011)
Okhotin, A.: Conjunctive grammars. Journal of Automata, Languages and Combinatorics 6(4), 519–535 (2001)
Okhotin, A.: On the equivalence of linear conjunctive grammars to trellis automata. RAIRO Informatique Théorique et Applications 38(1), 69–88 (2004)
Okhotin, A.: Conjunctive and Boolean grammars: the true general case of the context-free grammars. Computer Science Review 9, 27–59 (2013)
Okhotin, A.: Improved normal form for grammars with one-sided contexts. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 205–216. Springer, Heidelberg (2013)
Rogers Jr., H.: Theory of Recursive Functions and Effective Computability (1967)
Rounds, W.C.: LFP: A logic for linguistic descriptions and an analysis of its complexity. Computational Linguistics 14(4), 1–9 (1988)
Terrier, V.: On real-time one-way cellular array. Theoretical Computer Science 141(1-2), 331–335 (1995)
Törmä, I.: Personal communication (February 2013)
Yu, S.: A property of real-time trellis automata. Discrete Applied Mathematics 15(1), 117–119 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barash, M., Okhotin, A. (2014). Linear Grammars with One-Sided Contexts and Their Automaton Representation. In: Pardo, A., Viola, A. (eds) LATIN 2014: Theoretical Informatics. LATIN 2014. Lecture Notes in Computer Science, vol 8392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54423-1_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-54423-1_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54422-4
Online ISBN: 978-3-642-54423-1
eBook Packages: Computer ScienceComputer Science (R0)