Open AccessAxiomatizing Omega and Omega-op Powers of Words
Author(s) -
Stephen L. Bloom,
Zoltán Ésik
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i41.21756
Subject(s) - omega , decidability , axiom , simple (philosophy) , set (abstract data type) , mathematics , product (mathematics) , power (physics) , polynomial , discrete mathematics , combinatorics , computer science , physics , mathematical analysis , programming language , philosophy , geometry , epistemology , quantum mechanics
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.