A4 Vertaisarvioitu artikkeli konferenssijulkaisussa

Linear grammars with one-sided contexts and their automaton representation




TekijätAlexander Okhotin, Mikhail Barash

Konferenssin vakiintunut nimiInternational symposium on latin american theoretical informatics

Julkaisuvuosi2014

JournalLecture Notes in Computer Science

Sarjan nimiLNCS

Numero sarjassa8392

Vuosikerta8392

Aloitussivu190

Lopetussivu201

Sivujen määrä12

ISSN0302-9743

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


Tiivistelmä

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