Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Language equations with all Boolean operations and concatenation and a particular order on the set of solutions are proved to be equal in expressive power to the first-order Peano arithmetic, In particular, it is shown that the class of sets representable using k variables (for every k ≥ 2) is exactly the k-th level of the arithmetical hierarchy, i.e., the sets definable by recursive predicates with k alternating quantifiers. The property of having an extremal solution is shown to be nonrepresentable in first-order arithmetic.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 985-998 |
Число страниц | 14 |
Журнал | International Journal of Foundations of Computer Science |
Том | 16 |
Номер выпуска | 5 |
DOI | |
Состояние | Опубликовано - 1 окт 2005 |
Опубликовано для внешнего пользования | Да |
ID: 41141132