Unambiguous conjunctive grammars over a one-letter alphabet

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

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

Аннотация

It is demonstrated that unambiguous conjunctive grammars over a unary alphabet ∑ = {a} have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base k ≥ 11 and for every one-way real-time cellular automaton operating over the alphabet of base-k digits {⌊k+9/4⌋,..., ⌊k+1/2⌋}, the language of all strings an with the base-k notation of the form 1 w 1, where w is accepted by the automaton, is generated by an unambiguous conjunctive grammar. Another encoding is used to simulate a cellular automaton in a unary language containing almost all strings. These constructions are used to show that for every fixed unambiguous conjunctive language L0, testing whether a given unambiguous conjunctive grammar generates L0 is undecidable.

Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory - 17th International Conference, DLT 2013, Proceedings
Страницы277-288
Число страниц12
DOI
СостояниеОпубликовано - 19 сен 2013
Событие17th International Conference on Developments in Language Theory, DLT 2013 - Marne-la-Vallee, Франция
Продолжительность: 18 июн 201321 июн 2013

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

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

конференция

конференция17th International Conference on Developments in Language Theory, DLT 2013
СтранаФранция
ГородMarne-la-Vallee
Период18/06/1321/06/13

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

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

Fingerprint Подробные сведения о темах исследования «Unambiguous conjunctive grammars over a one-letter alphabet». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать