Axiomatizing Omega and Omega-op Powers of Words | Zendy

Stephen L. Bloom | Zendy; Zoltán Ésik | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Axiomatizing 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research