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
Voir la notice de l'article provenant de la source Numdam
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},
mrnumber = {2059025},
zbl = {1082.68070},
language = {en},
url = {http://geodesic.mathdoc.fr/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 SP - 3 EP - 17 VL - 38 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2004005/ DO - 10.1051/ita:2004005 LA - en ID - ITA_2004__38_1_3_0 ER -
%0 Journal Article %A Bloom, Stephen L. %A Ésik, Zoltán %T Axiomatizing omega and omega-op powers of words %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2004 %P 3-17 %V 38 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2004005/ %R 10.1051/ita:2004005 %G en %F 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) no. 1, pp. 3-17. doi: 10.1051/ita:2004005
Cité par Sources :