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

: Okhotin A, Rondogiannis P

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2012

: Information and Computation

: INFORMATION AND COMPUTATION

: INFORM COMPUT

: 212

: 1

: 14

: 0890-5401

DOI: https://doi.org/10.1016/j.ic.2012.01.004

Equations of the form X = phi(X) are considered, where the unknown X is a set of natural numbers. The expression phi(X) may contain the operations of set addition, defined as S + T = {m + n vertical bar m is an element of S, n is an element of 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. (C) 2012 Elsevier Inc. All rights reserved.