RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 2002, том 41, номер 5, страницы 610–631 (Mi al200)

Эта публикация цитируется в 1 статье

О разрешимости классов иерархий регулярных апериодических языков

В. Л. Селиванов

Новосибирский государственный педагогический университет

Аннотация: Предлагается новый, логический подход к проблеме разрешимости для иерархий Страубинга и Бжозовского, основанный на теоремах об устойчивости из теории моделей, на одной теореме Хигмана и на теореме Рабина о дереве. Таким путем удается получить чисто логические короткие доказательства некоторых известных фактов о разрешимости, что может представлять определенный методологический интерес. Данный подход применим также в некоторых других подобных ситуациях, например, для иерархий формул по модулю теории линейных порядков с конечным числом унарных предикатов.

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

УДК: 510.532+519.713.2

Поступило: 25.12.2000
Окончательный вариант: 18.05.2001


 Англоязычная версия: Algebra and Logic, 2002, 41:5, 337–348

Реферативные базы данных:


© МИАН, 2024