Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Equations of the form X=φ(X) are considered, where the unknown X is a set of natural numbers. The expression φ(X) may contain the operations of set addition, defined as S+T={m+n|m ∑ S,n ∑ 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.
| Язык оригинала | английский |
|---|---|
| Страницы (с-по) | 1-14 |
| Число страниц | 14 |
| Журнал | Information and Computation |
| Том | 212 |
| DOI | |
| Состояние | Опубликовано - 1 мар 2012 |
ID: 41139882