|
Axiomatizing Omega and Omega-op Powers of Words
Stephen L. Bloom
October 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
Available as PostScript, PDF, DVI. |