A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the expressive power of univariate equations over sets of natural numbers
Tekijät: Okhotin A, Rondogiannis P
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2012
Journal: Information and Computation
Tietokannassa oleva lehden nimi: INFORMATION AND COMPUTATION
Lehden akronyymi: INFORM COMPUT
Vuosikerta: 212
Aloitussivu: 1
Lopetussivu: 14
Sivujen määrä: 14
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2012.01.004
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali