Linear grammars with one-sided contexts and their automaton representation

Mikhail Barash, Alexander Okhotin

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

3 Цитирования (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 σ02-completeness of the finiteness problem for these grammars.

Язык оригиналаанглийский
Название основной публикацииLATIN 2014
Подзаголовок основной публикацииTheoretical Informatics - 11th Latin American Symposium, Proceedings
ИздательSpringer Nature
Страницы190-201
Число страниц12
ISBN (печатное издание)9783642544224
DOI
СостояниеОпубликовано - 1 янв 2014
Событие11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Уругвай
Продолжительность: 31 мар 20144 апр 2014

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том8392 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция11th Latin American Theoretical Informatics Symposium, LATIN 2014
СтранаУругвай
ГородMontevideo
Период31/03/144/04/14

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

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

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

Цитировать