DOI

Equations of the form X=φ(X) are considered, where the unknown X is a set of natural numbers. The expression φ(X) may contain the operations of set addition, defined as S+T={m+n|m ∑ S,n ∑ T}, union, intersection, as well as ultimately periodic constants. An equation with a non-periodic solution of exponential growth rate is constructed. At the same time it is demonstrated that no sets with super-exponential growth rate can be represented. It is also shown that restricted classes of these equations cannot represent sets with super-linearly growing complements nor sets that are additive bases of order 2. The results have direct implications on the power of unary conjunctive grammars with one nonterminal symbol.

Язык оригиналаанглийский
Страницы (с-по)1-14
Число страниц14
ЖурналInformation and Computation
Том212
DOI
СостояниеОпубликовано - 1 мар 2012

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

  • Теоретические компьютерные науки
  • Информационные системы
  • Прикладные компьютерные науки
  • Математика и теория расчета

ID: 41139882