# Axiomatizing omega and omega-op powers of words

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topBloom, Stephen L., and Ésik, Zoltán. "Axiomatizing omega and omega-op powers of words." RAIRO - Theoretical Informatics and Applications 38.1 (2010): 3-17. <http://eudml.org/doc/92732>.

@article{Bloom2010,

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},

language = {eng},

month = {3},

number = {1},

pages = {3-17},

publisher = {EDP Sciences},

title = {Axiomatizing omega and omega-op powers of words},

url = {http://eudml.org/doc/92732},

volume = {38},

year = {2010},

}

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

DA - 2010/3//

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/92732

ER -

## References

top- N. Bedon, Finite automata and ordinals. Theoret. Comput. Sci.156 (1996) 119-144.
- 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.
- S.L. Bloom and C. Choffrut, Long words: the theory of concatenation and ω-power. Theoret. Comput. Sci.259 (2001) 533-548.
- S.L. Bloom and Z. Ésikn, Iteration Theories. Springer (1993).
- S.L. Bloom and Z. Ésik, Deciding whether the frontier of a regular tree is scattered. Fundamenta Informaticae55 (2003) 1-21.
- 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.
- 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.
- 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.
- 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.
- Y. Choueka, Finite automata, definable sets, and regular expressions over ωn-tapes. J. Comp. Syst. Sci.17 (1978) 81-97.
- B. Courcelle, Frontiers of infinite trees. RAIRO: Theoret. Informatics Appl./Theor. Comput. Sci.12 (1978) 319-337.
- Z. Ésik and A. Labella, Equational properties of iteration in algebraically complete categories. Theoret. Comput. Sci.195 (1998) 61-89.
- S. Heilbrunner, An algorithm for the solution of fixed-point equations for infinite words. RAIRO: Theoret. Informatics Appl.14 (1980) 131-141.
- J.B. Rosenstein, Linear Orderings. Academic Press, New York (1982).
- W. Thomas, On frontiers of regular trees. RAIRO: Theoret. Informatics Appl.20 (1986) 371-381.
- Th. Wilke, An algebraic theory for regular languages of finite and infinite words. Int. J. Algebra Comput.3 (1993) 447-489.
- J. Wojciechowski, Finite automata on transfinite sequences and regular expressions. Fundamenta Informaticae8 (1985) 379-396.

## NotesEmbed ?

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