A1 Refereed original research article in a scientific journal
On the expressive power of univariate equations over sets of natural numbers
Authors: Okhotin A, Rondogiannis P
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2012
Journal: Information and Computation
Journal name in source: INFORMATION AND COMPUTATION
Journal acronym: INFORM COMPUT
Volume: 212
First page : 1
Last page: 14
Number of pages: 14
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2012.01.004
Abstract
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.
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.
UTU Research Portal