Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Unambiguous Conjunctive Gramma...

Unambiguous Conjunctive Grammars Over a One-Letter Alphabet

Artur Jez, Alexander Okhotin, Unambiguous Conjunctive Grammars Over a One-Letter Alphabet. TUCS Technical Reports 1043, Turku Centre for Computer Science, 2012.

Abstract:

It is demonstrated that unambiguous conjunctive grammars over a unary alphabet $\Sigma=\{a\}$ have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base $k \ge 11$ and for every one-way real-time cellular automaton operating over the alphabet of base-$k$ digits $\big\{\lceil\frac{k+9}{4}\rceil, \ldots, \lfloor\frac{k+1}{2} \rfloor\big\}$, the language of all strings $a^n$ with the base-$k$ notation of the form $1w1$, 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 $L_0$, testing whether a given unambiguous conjunctive grammar generates $L_0$ is undecidable.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tJeOk12a,
  title = {Unambiguous Conjunctive Grammars Over a One-Letter Alphabet},
  author = {Jez, Artur and Okhotin, Alexander},
  number = {1043},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2012},
  keywords = {Conjunctive grammars, ambiguity, language equations, unary languages},
  ISBN = {978-952-12-2733-2},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication