Аннотация:
Мы рассматриваем алгебру всех конечных языков над многосимвольным алфавитом с операцией конкатенации. Ранее было показано, что если взять подобную алгебру, но состоящую из всех регулярных многосимвольных языков, то в ней можно интерпретировать алгебру регулярных односимвольных языков, откуда следует, что теория обеих этих алгебр эквивалентна элементарной арифметике. В настоящей работе мы доказываем аналогичный результат для алгебры конечных языков: в ней определима подалгебра односимвольных языков, а сама она имеет теорию алгоритмически эквивалентную элементарной арифметике.
Ключевые слова:
язык, конечный язык, конкатенация, элементарная арифметика.
Работа выполнена при финансовой поддержке РФФИ, проект 20-01-00435.
Поступила в редакцию: 08.10.2020 Исправленный вариант: 20.10.2020
Реферативные базы данных:
Тип публикации:
Статья
УДК:
510.665, 519.765
Образец цитирования:
С. М. Дудаков, “Об определимости в алгебре конечных языков с конкатенацией множества односимвольных языков”, Вестник ТвГУ. Серия: Прикладная математика, 2020, № 4, 5–13
\RBibitem{Dud20}
\by С.~М.~Дудаков
\paper Об определимости в алгебре конечных языков с конкатенацией множества односимвольных языков
\jour Вестник ТвГУ. Серия: Прикладная математика
\yr 2020
\issue 4
\pages 5--13
\mathnet{http://mi.mathnet.ru/vtpmk601}
\crossref{https://doi.org/10.26456/vtpmk601}
\elib{https://elibrary.ru/item.asp?id=44503256}
Цитирование в формате AMSBIB
Обратная связь: