On Decidability of Regular Languages Theories

摘要

This paper is dedicated to studying decidability properties of some regular languages theories. We prove that the regular languages theory with the Kleene star only is decidable. If we use union and concatenation simultaneously then the theory becomes both Σ_1- and Π_1-hard over the one-symbol alphabet. Finally, we prove that the regular languages theory over one-symbol alphabet with union and the Kleene star is equivalent to arithmetic. The Kleene star is definable with union and concatenation, hence, the previous theory is equivalent to arithmetic also.