Об определимости в алгебре конечных языков с конкатенацией множества односимвольных языков

Дудаков, С.М.

Об определимости в алгебре конечных языков с конкатенацией множества односимвольных языков

Дата публикации: 2020

Дата публикации в реестре: 2021-01-19T20:12:15Z

Аннотация:

Мы рассматриваем алгебру всех конечных языков над многосимвольным алфавитом с операцией конкатенации. Ранее было показано, что если взять подобную алгебру, но состоящую из всех регулярных многосимвольных языков, то в ней можно интерпретировать алгебру регулярных односимвольных языков, откуда следует, что теория обеих этих алгебр эквивалентна элементарной арифметике. В настоящей работе мы доказываем аналогичный результат для алгебры конечных языков: в ней определима подалгебра односимвольных языков, а сама она имеет теорию алгоритмически эквивалентную элементарной арифметике

Ключевые слова:
510.665 Проблемы разрешения, 519.76 Математические вопросы семиотики

Тип: Статья