|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Теоретические основы информатики
Об определимости в алгебре конечных языков с конкатенацией множества односимвольных языков
С. М. Дудаков Тверской государственный университет, г. Тверь
Аннотация:
Мы рассматриваем алгебру всех конечных языков над многосимвольным алфавитом с операцией конкатенации. Ранее было показано, что если взять подобную алгебру, но состоящую из всех регулярных многосимвольных языков, то в ней можно интерпретировать алгебру регулярных односимвольных языков, откуда следует, что теория обеих этих алгебр эквивалентна элементарной арифметике. В настоящей работе мы доказываем аналогичный результат для алгебры конечных языков: в ней определима подалгебра односимвольных языков, а сама она имеет теорию алгоритмически эквивалентную элементарной арифметике.
Ключевые слова:
язык, конечный язык, конкатенация, элементарная арифметика.
Поступила в редакцию: 08.10.2020 Исправленный вариант: 20.10.2020
Образец цитирования:
С. М. Дудаков, “Об определимости в алгебре конечных языков с конкатенацией множества односимвольных языков”, Вестник ТвГУ. Серия: Прикладная математика, 2020, № 4, 5–13
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vtpmk601 https://www.mathnet.ru/rus/vtpmk/y2020/i4/p5
|
Статистика просмотров: |
Страница аннотации: | 207 | PDF полного текста: | 133 | Список литературы: | 20 |
|