DOI

It has recently been proved (Jeż, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some non-regular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as non-existence of a recursive function bounding the growth rate of the generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.

Язык оригиналаанглийский
Страницы (с-по)27-58
Число страниц32
ЖурналTheory of Computing Systems
Том46
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2009

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

  • Теоретические компьютерные науки
  • Математика и теория расчета

ID: 41141736