首页|On Decidability of Theories of Regular Languages
On Decidability of Theories of Regular Languages
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
NSTL
Springer Nature
This paper is dedicated to studying decidability properties of theories of regular languages with classical operations: union, concatenation, and the Kleene star. The theory with union only is a theory of some Boolean algebra, so it is decidable. We prove that the theory of regular languages with the Kleene star only is decidable. If we use union and concatenation simultaneously, then the theory becomes both sigma(1)- and pi(1)-hard over the one-symbol alphabet. Using methods from the proof of this theorem we establish that the theory of regular languages over one-symbol alphabet with union and the Kleene star is as hard as arithmetic. Then we establish that the theory with all three operations is reducible to arithmetic also, hence, it is equivalent to arithmetic. Finally, we prove that the theory of regular languages over any alphabet with concatenation only is equivalent to arithmetic also. The last result is based on our previous work where an analogous theorem was proved for one-symbol languages.
NETL
NSTL
Springer Nature
