Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

Axiomatizing omega and omega-op powers of words

Stephen L. BloomZoltán Ésik — 2004

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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.

Axiomatizing omega and omega-op powers of words

Stephen L. BloomZoltán Ésik — 2010

RAIRO - Theoretical Informatics and Applications

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.

Page 1

Download Results (CSV)