• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Linear Grammars with One-Sided Contexts and Their Automaton Representation

Mikhail Barash, Alexander Okhotin, Linear Grammars with One-Sided Contexts and Their Automaton Representation. TUCS Technical Reports 1088, TUCS, 2013.

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

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tBaOk13a,
  title = {Linear Grammars with One-Sided Contexts and Their Automaton Representation},
  author = {Barash, Mikhail and Okhotin, Alexander},
  number = {1088},
  series = {TUCS Technical Reports},
  publisher = {TUCS},
  year = {2013},
  keywords = {Context-free grammars, conjunctive grammars, context-sensitive grammars, cellular automata, undecidability},
  ISBN = {978-952-12-2928-2},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication