Open AccessOn definability of one-symbol languages in the monoid of finite languages with concatenation
Author(s) -
Сергей Михайлович Дудаков
Publication year - 2020
Publication title -
vestnik tverskogo gosudarstvennogo universiteta. seriâ prikladnaâ matematika
Language(s) - English
Resource type - Journals
ISSN - 1995-0136
DOI - 10.26456/vtpmk601
Subject(s) - symbol (formal) , concatenation (mathematics) , regular language , abstract family of languages , subalgebra , mathematics , free monoid , algebra over a field , arithmetic , monoid , computer science , discrete mathematics , pure mathematics , theoretical computer science , programming language , automaton , second generation programming language , inductive programming , programming paradigm
Мы рассматриваем алгебру всех конечных языков над многосимвольным алфавитом с операцией конкатенации. Ранее было показано, что если взять подобную алгебру, но состоящую из всех регулярных многосимвольных языков, то в ней можно интерпретировать алгебру регулярных односимвольных языков, откуда следует, что теория обеих этих алгебр эквивалентна элементарной арифметике. В настоящей работе мы доказываем аналогичный результат для алгебры конечных языков: в ней определима подалгебра односимвольных языков, а сама она имеет теорию алгоритмически эквивалентную элементарной арифметике. We consider an algebra of all finite languages with the concatenation operation. For one-symbol languages it is known that its theory is equivalent to the first-order arithmetic. Earlier it was proved that for regular languages a one-symbol algebra can be interpreted in multi-symbol algebras. Here we show how to define a one-symbol subalgebra in multi-symbol algebras for finite languages.