×

Linear grammars with one-sided contexts and their automaton representation. (English) Zbl 1328.68100

Summary: 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 and automata.

MSC:

68Q42 Grammars and rewriting systems
68Q80 Cellular automata (computational aspects)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] T. Aizikowitz and M. Kaminski, . Comput. Sci. Russia (CSR 2011, St. Petersburg, Russia, 14-18 June 2011). Vol. 6651 of Lect. Notes Comput. Sci. (2011) 345-358.
[2] M. Barash, Recursive descent parsing for grammars with contexts. SOFSEM 2013 student research forum Špindleruv Mlýn, Czech Republic, 26-31 January, 2013. Local Proceedings II, 10-21, Institute of Computer Science AS CR (2013).
[3] M. Barash, Programming language specification by a grammar with contexts. In Fifth Workshop on Non-Classical Models of Automata and Applications, NCMA 2013, Umeå, Sweden, 13-14 August, 2013, edited by S. Bensch, F. Drewes, R. Freund, F. Otto. books@ocg.at 294, Österreichische Computer Gesellschaft (2013) 51-67.
[4] M. Barash and A. Okhotin, . Inform. Comput.237 (2014) 268-293. · Zbl 1360.68531
[5] M. Barash and A. Okhotin, LATIN 2014: Theoretical Informatics, Montevideo, Uruguay, 31 March-4 April 2014. In vol. 8392, Lect. Notes Comput. Sci. (2014) 190-201.
[6] A. Birman and J.D. Ullman, . Inform. Control23 (1973) 1-34. · Zbl 0296.68019
[7] K. Čulík II, J. Gruska and A. Salomaa, Systolic trellis automata I. Int. J. Comput. Math.15 (1984) 195-212. · Zbl 0571.68041
[8] K. Čulík II, J. Gruska and A. Salomaa, Systolic trellis automata II. Int. J. Comput. Math.16 (1984) 3-22. · Zbl 0571.68042
[9] C. Dyer, . Inform. Control44 (1980) 261-281. · Zbl 0442.68082
[10] O.H. Ibarra and S.M. Kim, . Theoret. Comput. Sci.29 (1984) 123-153. · Zbl 0536.68048
[11] O.H. Ibarra, S.M. Kim and S. Moran, SIAM J. Comput.14 (1985) 426-447. · Zbl 0574.68044
[12] A. Je\.z, . Int. J. Found. Comput. Sci.19 (2008) 597-615. · Zbl 1155.68040
[13] A. Je\.z and A. Okhotin, Theory Comput. Syst.46 (2010) 27-58. · Zbl 1183.68327
[14] R. Kowalski, Logic for Problem Solving. North-Holland, Amsterdam (1979).
[15] A. Okhotin, Conjunctive grammars. J. Autom. Lang. Comb.6 (2001) 519-535. · Zbl 1004.68082
[16] A. Okhotin, . Theoret. Comput. Sci.299 (2003) 663-685. · Zbl 1042.68069
[17] A. Okhotin, . RAIRO: ITA38 (2004) 69-88.
[18] A. Okhotin, Homomorphisms preserving linear conjunctive languages. J. Autom. Lang. Comb.13 (2008) 299-305. · Zbl 1193.68156
[19] A. Okhotin, Comput. Sci. Rev.9 (2013) 27-59. · Zbl 1286.68268
[20] A. Okhotin, Improved normal form for grammars with one-sided contexts. Theoret. Comput. Sci.588 (2015) 52-72. · Zbl 1329.68155
[21] H. Rogers, Jr., Theory of Recursive Functions and Effective Computability. McGraw-Hill (1967). · Zbl 0183.01401
[22] W.C. Rounds, LFP: A logic for linguistic descriptions and an analysis of its complexity. Comput. Linguistics14 (1988) 1-9.
[23] V. Terrier, . Theoret. Comput. Sci.141 (1995) 331-335. · Zbl 0873.68114
[24] I. Törmä. Personal communication. February 2013.
[25] S. Yu, Discrete Appl. Math.15 (1986) 117-119. · Zbl 0597.68048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.