| Issue |
RAIRO-Theor. Inf. Appl.
Volume 49, Number 2, April-June 2015
|
|
|---|---|---|
| Page(s) | 153 - 178 | |
| DOI | https://doi.org/10.1051/ita/2015004 | |
| Published online | 08 July 2015 | |
Linear grammars with one-sided contexts and their automaton representation∗
1 Turku Centre for Computer Science, Turku 20014, Finland.
mikbar@utu.fi
2 Department of Mathematics and Statistics, University of Turku, Turku 20014, Finland.
Received: 5 December 2014
Accepted: 11 June 2015
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 Σ02-completeness of the finiteness problem for these grammars and automata.
Mathematics Subject Classification: 68Q42 / 68Q80
Key words: Context-free grammars / conjunctive grammars / contexts / cellular automata / trellis automata / undecidability.
© EDP Sciences 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.