Article contents
Axiomatizing omega and omega-op powers of words
Published online by Cambridge University Press: 15 March 2004
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.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2004
References
- 7
- Cited by