Axiomatizing omega and omega-op powers of words

Stephen L. Bloom; Zoltán Ésik

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2004)

  • Volume: 38, Issue: 1, page 3-17
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Bloom, Stephen L., and Ésik, Zoltán. "Axiomatizing omega and omega-op powers of words." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 38.1 (2004): 3-17. <http://eudml.org/doc/245710>.

@article{Bloom2004,
abstract = {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.},
author = {Bloom, Stephen L., Ésik, Zoltán},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {1},
pages = {3-17},
publisher = {EDP-Sciences},
title = {Axiomatizing omega and omega-op powers of words},
url = {http://eudml.org/doc/245710},
volume = {38},
year = {2004},
}

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
PB - EDP-Sciences
VL - 38
IS - 1
SP - 3
EP - 17
AB - 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.
LA - eng
UR - http://eudml.org/doc/245710
ER -

References

top
  1. [1] N. Bedon, Finite automata and ordinals. Theoret. Comput. Sci. 156 (1996) 119-144. Zbl0871.68127MR1382843
  2. [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. Zbl0906.20045
  3. [3] S.L. Bloom and C. Choffrut, Long words: the theory of concatenation and ω -power. Theoret. Comput. Sci. 259 (2001) 533-548. Zbl0972.68106MR1832808
  4. [4] S.L. Bloom and Z. Ésikn, Iteration Theories. Springer (1993). Zbl0773.03033MR1295433
  5. [5] S.L. Bloom and Z. Ésik, Deciding whether the frontier of a regular tree is scattered. Fundamenta Informaticae 55 (2003) 1-21. Zbl1066.68060MR2000082
  6. [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. Zbl0999.68100MR1907015
  7. [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. Zbl1015.68092MR2177336
  8. [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. MR183636
  9. [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. Zbl0207.31001MR210593
  10. [10] Y. Choueka, Finite automata, definable sets, and regular expressions over ω n -tapes. J. Comp. Syst. Sci. 17 (1978) 81-97. Zbl0386.03018MR489032
  11. [11] B. Courcelle, Frontiers of infinite trees. RAIRO: Theoret. Informatics Appl./Theor. Comput. Sci. 12 (1978) 319-337. Zbl0411.68065MR517634
  12. [12] Z. Ésik and A. Labella, Equational properties of iteration in algebraically complete categories. Theoret. Comput. Sci. 195 (1998) 61-89. Zbl0903.18003MR1603831
  13. [13] S. Heilbrunner, An algorithm for the solution of fixed-point equations for infinite words. RAIRO: Theoret. Informatics Appl. 14 (1980) 131-141. Zbl0433.68062MR581673
  14. [14] J.B. Rosenstein, Linear Orderings. Academic Press, New York (1982). Zbl0488.04002MR662564
  15. [15] W. Thomas, On frontiers of regular trees. RAIRO: Theoret. Informatics Appl. 20 (1986) 371-381. Zbl0639.68071MR880841
  16. [16] Th. Wilke, An algebraic theory for regular languages of finite and infinite words. Int. J. Algebra Comput. 3 (1993) 447-489. Zbl0791.68116MR1250247
  17. [17] J. Wojciechowski, Finite automata on transfinite sequences and regular expressions. Fundamenta Informaticae 8 (1985) 379-396. Zbl0573.68045MR810708

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.