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

详细信息    查看全文

• 作者：Alexander Okhotin^a ; ¹ ; ^{alexander.okhotin@utu.fi} ; Panos Rondogiannis^b ; ² ; ^{prondo@di.uoa.gr}
• 关键词：Non-periodic sets of natural numbers ; Language equations ; Conjunctive grammars
• 刊名：Information and Computation
• 出版年：2012
• 出版时间：March 2012
• 年：2012
• 卷：212
• 期：Complete
• 页码：1-14
• 全文大小：227 K

文摘

Equations of the form are considered, where the unknown X is a set of natural numbers. The expression may contain the operations of set addition, defined as , 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.