Axiomatizing omega and omega-op powers of words
Department of Computer Science Stevens Institute of Technology
Hoboken, NJ 07030; firstname.lastname@example.org.
2 Institute for Informatics University of Szeged 6720 Szeged, Hungary
Accepted: 10 October 2003
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.
Mathematics Subject Classification: 06F99 / 03B25
© EDP Sciences, 2004