Н. С. Винокуров, “Индексные множества классов автоматных структур”, Сиб. матем. журн., 2006, том 47, номер 5,страницы 1019

Индексные множества классов автоматных структур

Н. С. Винокуров

Новосибирский государственный университет, механико-математический факультет

Аннотация: Получены точные оценки в арифметической и аналитической иерархиях индексных множеств различных классов автоматных моделей. Также получены оценки проблем существования вычислимого изоморфизма и вложения для автоматных структур.

Ключевые слова: автоматная модель, индексное множество, проблема вычислимого изоморфизма, однородность, универсальность.

УДК: 510.51, 519.716.35

Статья поступила: 18.05.2005
Окончательный вариант: 22.03.2006