DOI

Conjunctive grammars over an alphabet ∑ = {a} are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X = φ(X) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple nonterminals can be encoded into a grammar with a single nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-nonterminal conjunctive grammars over {a} is proved to be EXPTIME-complete, while the equivalence, finiteness and emptiness problems for these grammars are shown to be undecidable.

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings
Страницы191-202
Число страниц12
DOI
СостояниеОпубликовано - 2009
Опубликовано для внешнего пользованияДа
Событие4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk, Российская Федерация
Продолжительность: 18 авг 200923 авг 2009

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

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

конференция

конференция4th International Computer Science Symposium in Russia, CSR 2009
Страна/TерриторияРоссийская Федерация
ГородNovosibirsk
Период18/08/0923/08/09

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

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

ID: 78935797