Unambiguous conjunctive grammars over a one-letter alphabet

Research outputpeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 17th International Conference, DLT 2013, Proceedings
Pages277-288
Number of pages12
DOIs
Publication statusPublished - 19 Sep 2013
Event17th International Conference on Developments in Language Theory, DLT 2013 - Marne-la-Vallee
Duration: 18 Jun 201321 Jun 2013

Publication series

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

Conference

Conference17th International Conference on Developments in Language Theory, DLT 2013
CountryFrance
CityMarne-la-Vallee
Period18/06/1321/06/13

Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Unambiguous conjunctive grammars over a one-letter alphabet'. Together they form a unique fingerprint.

Cite this