A4 Refereed article in a conference publication

Linear grammars with one-sided contexts and their automaton representation




AuthorsAlexander Okhotin, Mikhail Barash

Conference nameInternational symposium on latin american theoretical informatics

Publication year2014

JournalLecture Notes in Computer Science

Series titleLNCS

Number in series8392

Volume8392

First page 190

Last page201

Number of pages12

ISSN0302-9743

DOIhttps://doi.org/10.1007/978-3-642-54423-1_17


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.



Last updated on 2024-26-11 at 18:53