On Undecidability of Concatenation Theory for One-Symbol Languages
Sergey Mikhailovich Dudakov · Lobachevskii Journal of Mathematics · 2020
Abstract We investigate concatenation theories for some classes of one-symbol languages. These classes can be the class of all languages, the class of regular languages, or the class of finite languages. We prove that all such theories are undecidable. The last two theories are algorithmically equivalent to elementary arithmetic. The first is equivalent to second order arithmetic.