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.

Original languageEnglish
Pages (from-to)1-14
Number of pages14
JournalInformation and Computation
Volume212
DOIs
StatePublished - 1 Mar 2012

    Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

    Research areas

  • Conjunctive grammars, Language equations, Non-periodic sets of natural numbers

ID: 41139882