Axiomatizing omega and omega-op powers of words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) no. 1, pp. 3-17.

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},
     pages = {3--17},
     publisher = {EDP-Sciences},
     volume = {38},
     number = {1},
     year = {2004},
     doi = {10.1051/ita:2004005},
     zbl = {1082.68070},
     mrnumber = {2059025},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2004005/}
}
TY  - JOUR
AU  - Bloom, Stephen L.
AU  - Ésik, Zoltán
TI  - Axiomatizing omega and omega-op powers of words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2004
DA  - 2004///
SP  - 3
EP  - 17
VL  - 38
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2004005/
UR  - https://zbmath.org/?q=an%3A1082.68070
UR  - https://www.ams.org/mathscinet-getitem?mr=2059025
UR  - https://doi.org/10.1051/ita:2004005
DO  - 10.1051/ita:2004005
LA  - en
ID  - ITA_2004__38_1_3_0
ER  - 
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) no. 1, pp. 3-17. doi : 10.1051/ita:2004005. http://www.numdam.org/articles/10.1051/ita:2004005/

[1] N. Bedon, Finite automata and ordinals. Theoret. Comput. Sci. 156 (1996) 119-144. | MR 1382843 | Zbl 0871.68127

[2] N. Bedon and O. Carton, 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] S.L. Bloom and C. Choffrut, Long words: the theory of concatenation and ω-power. Theoret. Comput. Sci. 259 (2001) 533-548. | MR 1832808 | Zbl 0972.68106

[4] S.L. Bloom and Z. Ésikn, Iteration Theories. Springer (1993). | MR 1295433 | Zbl 0773.03033

[5] S.L. Bloom and Z. Ésik, Deciding whether the frontier of a regular tree is scattered. Fundamenta Informaticae 55 (2003) 1-21. | MR 2000082 | Zbl 1066.68060

[6] V. Bruyère and O. Carton, 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] V. Bruyère and O. Carton, 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] J.R. Büchi, 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] J.R. Büchi, 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] Y. Choueka, Finite automata, definable sets, and regular expressions over ω n -tapes. J. Comp. Syst. Sci. 17 (1978) 81-97. | MR 489032 | Zbl 0386.03018

[11] B. Courcelle, Frontiers of infinite trees. RAIRO: Theoret. Informatics Appl./Theor. Comput. Sci. 12 (1978) 319-337. | Numdam | MR 517634 | Zbl 0411.68065

[12] Z. Ésik and A. Labella, Equational properties of iteration in algebraically complete categories. Theoret. Comput. Sci. 195 (1998) 61-89. | MR 1603831 | Zbl 0903.18003

[13] S. Heilbrunner, 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] J.B. Rosenstein, Linear Orderings. Academic Press, New York (1982). | MR 662564 | Zbl 0488.04002

[15] W. Thomas, On frontiers of regular trees. RAIRO: Theoret. Informatics Appl. 20 (1986) 371-381. | Numdam | MR 880841 | Zbl 0639.68071

[16] Th. Wilke, 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] J. Wojciechowski, Finite automata on transfinite sequences and regular expressions. Fundamenta Informaticae 8 (1985) 379-396. | MR 810708 | Zbl 0573.68045

Cité par Sources :