In 1978, Courcelle asked for a complete set of axioms and rules for the equational theory of (discrete regular) words equipped with the operations of product, omega power and omega-op power. In this paper we find a simple set of equations and prove they are complete. Moreover, we show that the equational theory is decidable in polynomial time.
@article{ITA_2004__38_1_3_0,
author = {Bloom, Stephen L. and \'Esik, Zolt\'an},
title = {Axiomatizing omega and omega-op powers of words},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {38},
year = {2004},
pages = {3-17},
doi = {10.1051/ita:2004005},
mrnumber = {2059025},
zbl = {1082.68070},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2004__38_1_3_0}
}
Bloom, Stephen L.; Ésik, Zoltán. Axiomatizing omega and omega-op powers of words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) pp. 3-17. doi : 10.1051/ita:2004005. http://gdmltest.u-ga.fr/item/ITA_2004__38_1_3_0/
[1] , Finite automata and ordinals. Theoret. Comput. Sci. 156 (1996) 119-144. | MR 1382843 | Zbl 0871.68127
[2] and, An Eilenberg theorem for words on countable ordinals, in Latin'98: Theoretical Informatics, edited by C.L. Lucchesi and A.V. Moura. Lect. Notes Comput. Sci. 1380 (1998) 53-64. | Zbl 0906.20045
[3] and, Long words: the theory of concatenation and -power. Theoret. Comput. Sci. 259 (2001) 533-548. | MR 1832808 | Zbl 0972.68106
[4] and, Iteration Theories. Springer (1993). | MR 1295433 | Zbl 0773.03033
[5] and, Deciding whether the frontier of a regular tree is scattered. Fundamenta Informaticae 55 (2003) 1-21. | MR 2000082 | Zbl 1066.68060
[6] and, Automata on linear orderings, in Proc. Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. 2136 (2001) 236-247. | MR 1907015 | Zbl 0999.68100
[7] and, Hierarchy among automata on linear orderings, in Foundation of Information Technology in the Era of Network and Mobile Computing, Proc. TCS 2002. Kluwer Academic Publishers (2002) 107-118. | MR 2177336 | Zbl 1015.68092
[8] , On a decision method in restricted second-order arithmetic, in Int. Congress Logic, Methodology, and Philosophy of Science, Berkeley, 1960. Stanford University Press (1962) 1-11. | MR 183636
[9] , Transfinite automata recursions and weak second order theory of ordinals, in Int. Congress Logic, Methodology, and Philosophy of Science, Jerusalem, 1964. North Holland (1965) 2-23. | MR 210593 | Zbl 0207.31001
[10] , Finite automata, definable sets, and regular expressions over -tapes. J. Comp. Syst. Sci. 17 (1978) 81-97. | MR 489032 | Zbl 0386.03018
[11] , Frontiers of infinite trees. RAIRO: Theoret. Informatics Appl./Theor. Comput. Sci. 12 (1978) 319-337. | Numdam | MR 517634 | Zbl 0411.68065
[12] and, Equational properties of iteration in algebraically complete categories. Theoret. Comput. Sci. 195 (1998) 61-89. | MR 1603831 | Zbl 0903.18003
[13] , An algorithm for the solution of fixed-point equations for infinite words. RAIRO: Theoret. Informatics Appl. 14 (1980) 131-141. | Numdam | MR 581673 | Zbl 0433.68062
[14] , Linear Orderings. Academic Press, New York (1982). | MR 662564 | Zbl 0488.04002
[15] , On frontiers of regular trees. RAIRO: Theoret. Informatics Appl. 20 (1986) 371-381. | Numdam | MR 880841 | Zbl 0639.68071
[16] , An algebraic theory for regular languages of finite and infinite words. Int. J. Algebra Comput. 3 (1993) 447-489. | MR 1250247 | Zbl 0791.68116
[17] , Finite automata on transfinite sequences and regular expressions. Fundamenta Informaticae 8 (1985) 379-396. | MR 810708 | Zbl 0573.68045