Linear grammars with one-sided contexts and their automaton representation

Mikhail Barash, Alexander Okhotin

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

5 Цитирования (Scopus)


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 Σ2-completeness of the finiteness problem for these grammars and automata.

Язык оригиналаанглийский
Страницы (с-по)153-158
Число страниц6
ЖурналRAIRO - Theoretical Informatics and Applications
Номер выпуска2
СостояниеОпубликовано - 1 апр 2015

Предметные области Scopus

  • Программный продукт
  • Математика (все)
  • Прикладные компьютерные науки

Fingerprint Подробные сведения о темах исследования «Linear grammars with one-sided contexts and their automaton representation». Вместе они формируют уникальный семантический отпечаток (fingerprint).