TY - JOUR

T1 - On the expressive power of univariate equations over sets of natural numbers

AU - Okhotin, Alexander

AU - Rondogiannis, Panos

PY - 2012/3/1

Y1 - 2012/3/1

N2 - 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.

AB - 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.

KW - Conjunctive grammars

KW - Language equations

KW - Non-periodic sets of natural numbers

UR - http://www.scopus.com/inward/record.url?scp=84857268074&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2012.01.004

DO - 10.1016/j.ic.2012.01.004

M3 - Article

AN - SCOPUS:84857268074

VL - 212

SP - 1

EP - 14

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

ER -