Page 1 Next

Displaying 1 – 20 of 262

Showing per page

A Hierarchy of Automatic ω-Words having a Decidable MSO Theory

Vince Bárány (2008)

RAIRO - Theoretical Informatics and Applications

We investigate automatic presentations of ω-words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of ω-words enjoying the above...

A property of the solvable radical in finitely decidable varieties

Paweł M. Idziak, Matthew Valeriote (2001)

Fundamenta Mathematicae

It is shown that in a finitely decidable equational class, the solvable radical of any finite subdirectly irreducible member is comparable to all congruences of the irreducible if the type of the monolith is 2. In the type 1 case we establish that the centralizer of the monolith is strongly solvable.

Axiomatizing omega and omega-op powers of words

Stephen L. Bloom, Zoltá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. Bloom, Zoltá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.

Currently displaying 1 – 20 of 262

Page 1 Next