Автоматные и вычислимые упорядочиваемые множества

• Автор: Гаврюшкина, Александра Анатольевна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Новосибирск
• Количество страниц: 73 с.

Оглавление
Введение
1. Основные понятия
1.1. Разрешимые структуры
1.2. Некоторые сведения из теории конечных автоматов
1.3. Автоматные структуры
2. Линейные порядки
2.1. Предварительные сведения о линейных порядках
2.2. Автоматные линейные порядки
2.3. Разрешимые и автоматные линейные порядки
2.4. Некоторые примеры автоматных линейных порядков
3. Автоустойчивость
3.1. Для автоматных отношений эквивалентности
3.2. Для линейных порядков

4. Сложность автоматных частичных порядков
4.1. Сведение модели в конечной предикатной сигнатуре к частичному порядку
4.2. Сохранение автоматности
Литература

Введение
Объектами изучения математики являются модели (структуры) — множества с заданными на них отношениями и операциями. В середине прошлого столетия в работах А. Фрелиха, Д. Шефердсона, А. И. Мальцева, М. О. Рабина, Р. Воота и других появилось понятие вычислимой или конструктивной модели, то есть модели, которая может быть описана алгоритмически. С этого момента в математической логике образовалась новая подобласть — конструктивные модели, активное развитие которой продолжается до сих пор. Класс вычислимых моделей является наиболее общим и довольно сложным, в связи с этим возникло стремление выделить простейший с алгоритмической точки зрения подкласс вычислимых моделей. Одним из предложенных на эту роль классов является класс автоматных структур. Достоинства этого класса заключаются в том, что наиболее естественные проблемы и свойства автоматных моделей являются разрешимыми.
Упоминания такого рода моделей впервые появились в работах Дж. Р. Вюхи и М. О. Рабина [15], [16], [37], [38], которые изучали теорию конечных автоматов и рассматривали представления некоторых структур с помощью автоматов. С появлением в 1995 году статьи А. Нероуда и

<Ивепй(х,у) !=щ (х < у) & (Зг)(ж <з г) & (Зг)(2 < у) к, (/г)((х < г < у) —>
—* (Э-гх, 22)(л < г <3 £2)) — интервал х,у является дискретным с левым и правым концом.
тахсИвеп(1(х,у) <=; йгяепс^ж, у) & (/2)((г < х) —* ~^(1г8епс1(г,у)) &
&(Уг)((у < г) —> (Изепс1(х, г)) — интервал [х,у] является максимальным дискретным интервалом с левым и правым концом.
Итак, выпишем список аксиом Ах:
' 1) Ть — аксиомы линейного порядка.
2) Счетное число аксиом:
(Эх,у)Со(ж,2/), где Со(а:,у) <=; (Ив^х, у) & р/г)(х < 2);
(Зх,у)2(х,у), где 2(х,у) ^ (ж<Зг/)&(32)Со(г,ж);
(3х,у)С1(х,у), где С1 (х,у) — <1гв(х,у)&(3г)2(г,х);
(Бх,у)3(х,у), где 3(х,у) ±=; (ж < у)к(3г)(х <1 2 <3 у) & (32)0(2, ж);
{Зх,у)Сп{х,у), где С,п{х,у) ^ Фз(а:,2/)&(Э2)рп_1(2,а:);
(Зяг, т/)р„(гс, г/), где рп (х,у) ^ (ж < у) &
& (Згь ..., 2р„_г)(а: < «х < ... О гРп_2 <1 у) к. (32)С„-х(2, ж);
3) Аксиома (Ух)((3у)(у < х) —* (Зг)((ж <1 г) V (2 О ж))), утверждающая отсутствие плотных подинтервалов.