The equational theory of regular words
type: Item
instance of: scholarly article
title: The equational theory of regular words
zbMATH Open document ID: 1083.68072
author: Stephen L. Bloom
author: Zoltán Ésik
published in: Information and Computation
publication date: 2005-05-12T00:00:00Z
review text: 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.
reviewed by: Valentin Goranko
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 08A70
Mathematics Subject Classification ID: 03C05
zbMATH DE Number: 2167397
zbMATH Keywords: algebra of regular words
zbMATH Keywords: equational theory
zbMATH Keywords: axiomatization
zbMATH Keywords: decidability
zbMATH Keywords: free generation
zbMATH Keywords: variety
MaRDI profile type: Publication
full work available at URL: j.ic.2005.01.004
OpenAlex ID: W1991735660
cites work: Long words: The theory of concatenation and \(\omega\)-power
cites work: Q4454841
cites work: Axiomatizing omega and omega-op powers of words
cites work: Matrix and matricial iteration theories. I
cites work: Q4779147
cites work: Mathematical Foundations of Computer Science 2003
cites work: Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes
cites work: Q4198080
cites work: Automata, logics, and infinite games. A guide to current research
cites work: Q3871942
cites work: Q3949052
cites work: On frontiers of regular trees
DOI: 10.1016/J.IC.2005.01.004
Recommended article: AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
Recommended article: Duality and Equational Theory of Regular Languages
Recommended article: Q3753495
Recommended article: Equations over finite sets of words and equivalence problems in automata theory
Recommended article: Q4347966
Recommended article: FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
Recommended article: Two equational theories of partial words
Recommended article: Regular words and a theorem on sandwich algebras
Recommended article: A note on equations for commutative regular languages
Recommended article: Duality and the equational theory of regular languages.
description: scientific article; zbMATH DE number 2167397