The equational theory of regular words
Regular words, introduced by \textit{B. Courcelle} [``Frontiers of infinite trees, RAIRO, Inf. Théor. 12, 319--337 (1978; Zbl 0411.68065)], are (finite or infinite) words isomorphic to the frontier of regular binary trees with lexicographic ordering of the leaves. Regular words can be generated [see \textit{S. Heilbrunner}, ``An algorithm for the solution of fixed-point equations for infinite words, RAIRO, Inf. Théor. 14, 131--141 (1980; Zbl 0433.68062)] from singletons by applying the operations of concatenation, omega power, omega-op power, and shuffles. Following previous work of their own [``Axiomatizing omega and omega-op powers of words, Theor. Inform. Appl. 38, 3--17 (2004; Zbl 1082.68070)], the authors prove that the algebra of nonempty regular words on an alphabet \(A\), equipped with these operations, is freely generated by \(A\) in a variety which is completely axiomatized by an infinite collection of certain natural equations, and show that the equational theory of that variety is decidable in P-time and is not finitely based, thus solving open problems stated by Courcelle over 20 years ago.
- AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
- Duality and Equational Theory of Regular Languages
- scientific article; zbMATH DE number 3990879
- Equations over finite sets of words and equivalence problems in automata theory
- scientific article; zbMATH DE number 1047888
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Two equational theories of partial words
- Regular words and a theorem on sandwich algebras
- A note on equations for commutative regular languages
- Duality and the equational theory of regular languages.
- Automata, logics, and infinite games. A guide to current research
- Axiomatizing omega and omega-op powers of words
- Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes
- scientific article; zbMATH DE number 3675332 (Why is no real title available?)
- scientific article; zbMATH DE number 3767656 (Why is no real title available?)
- scientific article; zbMATH DE number 3639170 (Why is no real title available?)
- scientific article; zbMATH DE number 2053214 (Why is no real title available?)
- scientific article; zbMATH DE number 1834651 (Why is no real title available?)
- Long words: The theory of concatenation and -power
- Mathematical Foundations of Computer Science 2003
- Matrix and matricial iteration theories. I
- On frontiers of regular trees
- A Mezei-Wright theorem for categorical algebras
- On noncounting regular classes
- On a question of A. Salomaa The equational theory of regular expressions over a singleton alphabet is not finitely based
- Two equational theories of partial words
- An undecidable property of context-free linear orders
- Pro-aperiodic monoids via saturated models
- The ordinal generated by an ordinal grammar is computable
- Ordinal automata and Cantor normal form
- Closures in Binary Partial Algebras
- Isomorphism of regular trees and words
- Algebraic linear orderings
- The order type of scattered context-free orderings of rank one is computable
- Duality and Equational Theory of Regular Languages
- Regular and Algebraic Words and Ordinals
- On frontiers of regular trees
- scientific article; zbMATH DE number 169732 (Why is no real title available?)
- Axiomatizing omega and omega-op powers of words
- scientific article; zbMATH DE number 7453084 (Why is no real title available?)
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- On context-free languages of scattered words
- Long words: The theory of concatenation and -power
- Büchi context-free languages
- Automating the stable rank computation for special biserial algebras
- Equational theory of ordinals with addition and left multiplication by
- Test sets for equality of terms in the additive structure of ordinals augmented with right multiplication by
- Axiomatizing the equational theory of regular tree languages
This page was built for publication: The equational theory of regular words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1776401)
