On the expressive power of univariate equations over sets of natural numbers (Q418146)

This paper deals with one-variable equations of the form \(X=\varphi(X)\) over sets of natural numbers, where \(\varphi(X)\) is an expression, which may contain the operations of elementwise addition, union and intersection, as well as ultimately periodic constants. Such equations of a special form, where \(\varphi(X)\) is a union of intersections of sums of copies of \(X\) and singleton constants, correspond to one-nonterminal conjunctive grammars over a one-letter alphabet. By encoding the example of a non-regular unary conjunctive language due to \textit{A.~Jeż} [Int.\ J.\ Found.\ Comput.\ Sci.\ 19, No.\ 3, 597--615 (2008; Zbl 1155.68040)] into a unique solution of a one-variable equation, it is proved that sets of natural numbers generated by one-nonterminal conjunctive grammars need not be ultimately periodic and can have exponential growth rate. On the other hand, it is shown that a set of natural numbers cannot be obtained as the least solution of any equation \(X=\varphi(X)\), if the ratio between two consecutive elements of this set is not bounded (this covers, in particular, super-exponentially growing sets). This implies that one-nonterminal conjunctive grammars are less powerful than general conjunctive grammars. Further, it is proved that sets \(S\), for which \(S + S\) is co-finite, (in particular, dense sets) can be represented by one-nonterminal conjunctive grammars only if they are ultimately periodic. Finally, using a density argument, the set of all odd primes is also proved non-representable by one-nonterminal conjunctive grammars. These are the first results on non-representability of sets of low computational complexity by equations with union, intersection and addition.