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.

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings
Pages191-202
Number of pages12
DOIs
StatePublished - 2009
Externally publishedYes
Event4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk, Russian Federation
Duration: 18 Aug 200923 Aug 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5675 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Computer Science Symposium in Russia, CSR 2009
Country/TerritoryRussian Federation
CityNovosibirsk
Period18/08/0923/08/09

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 78935797