Axiomatizing Omega and Omega-op Powers of Words

Forfattere

  • Stephen L. Bloom
  • Zoltán Ésik

DOI:

https://doi.org/10.7146/brics.v9i41.21756

Resumé

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.

Downloads

Publiceret

2002-10-05

Citation/Eksport

Bloom, S. L., & Ésik, Z. (2002). Axiomatizing Omega and Omega-op Powers of Words. BRICS Report Series, 9(41). https://doi.org/10.7146/brics.v9i41.21756