Axiomatizing Omega and Omega-op Powers of Words

Authors :: Stephen L. Bloom
Zoltán Ésik
Source :: BRICS Report Series; No 41 (2002): RS-41 Axiomatizing Omega and Omega-op Powers of Words, BRICS Report Series; Nr. 41 (2002): RS-41 Axiomatizing Omega and Omega-op Powers of Words
Publication Year :: 2002
Publisher :: Aarhus University, 2002.
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.