Полнота и выразимость в классах линейных автоматов Часовских Анатолий Александрович

Краткое описание

Часовских, Анатолий Александрович.
Полнота и выразимость в классах линейных автоматов : диссертация ... доктора физико-математических наук : 01.01.09 / Часовских Анатолий Александрович; [Место защиты: ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова»]. - Москва, 2021. - 268 с.
Оглавление диссертациидоктор наук Часовских Анатолий Александрович
Введение
Глава 1. Постановка задач, вспомогательные классы
1.1. Линейный автомат, операции композиции
1.2. Аппроксимационная полнота
1.3. Класс одноместных ЛА, сохраняющих нулевую последовательность
Глава 2. Проблема полноты для линейных автоматов
2.1. Редукция
2.2. Приведенная ^-критериальная система
2.3. Об алгоритме проверки полноты
Глава 3. Замкнутые классы, содержащие сумматор
3.1. Необходимые понятия и обозначения
3.2. Замкнутые классы одноместных линейных автоматов, сохраняющих нулевую последовательность
3.3. Об алгоритме проверки выразимости через конечные множества
с сумматором
3.4. Выразимость сумматора через конечные множества
Глава 4. Аппроксимационная выразимость в классе линейных автоматов через множества, содержащие существенный автомат
4.1. Аппроксимационная выразимость в классе одноместных линейных автоматов, сохраняющих нулевую последовательность
4.2. Аппроксимационная выразимость через множества линейных автоматов с существенным автоматом, замыкания которых содержат все константы
4.3. Аппроксимационная выразимость всех констант через множества линейных автоматов, содержащие существенный автомат
4.4. Достаточные условия аппроксимационной выразимости
4.5. Об основаниях систем с сумматором, для которых выразимость
и аппроксимационная выразимость равносильны
4.6. Структура аппроксимационно замкнутых множеств линейных автоматов, содержащих сумматор в аппроксимационном замыкании
Глава 5. О полноте в некоторых содержательных классах
5.1. Линейные автоматы с операциями суперпозиции
5.2. Класс линейных 2-адических автоматов
Заключение
Список сокращений и условных обозначений
Список литературы