Axiomatizing Omega and Omega-op Powers of Words

Stephen L. Bloom, Zoltán Ésik

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.

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v9i41.21756
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library