|
Алгебра и логика, 2002, том 41, номер 5, страницы 610–631
(Mi al200)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О разрешимости классов иерархий регулярных апериодических языков
В. Л. Селиванов Новосибирский государственный педагогический университет
Аннотация:
Предлагается новый, логический подход к проблеме разрешимости для иерархий Страубинга и Бжозовского, основанный на теоремах об устойчивости из теории моделей, на одной теореме Хигмана и на теореме Рабина о дереве. Таким путем удается получить чисто логические короткие доказательства некоторых известных фактов о разрешимости, что может представлять определенный методологический интерес. Данный подход применим также в некоторых других подобных ситуациях, например, для иерархий формул по модулю теории линейных порядков с конечным числом унарных предикатов.
Ключевые слова:
разрешимость, иерархия Страубинга, иерархия Бжозовского, теорема устойчивости, регулярный апериодический язык.
Поступило: 25.12.2000 Окончательный вариант: 18.05.2001
Образец цитирования:
В. Л. Селиванов, “О разрешимости классов иерархий регулярных апериодических языков”, Алгебра и логика, 41:5 (2002), 610–631; Algebra and Logic, 41:5 (2002), 337–348
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al200 https://www.mathnet.ru/rus/al/v41/i5/p610
|
Статистика просмотров: |
Страница аннотации: | 250 | PDF полного текста: | 101 | Список литературы: | 44 | Первая страница: | 1 |
|