The word problem for \(\omega \)-terms over DA

DOI10.1016/j.tcs.2011.08.003zbMath1237.68117OpenAlexW1983052745MaRDI QIDQ650888

Ana Moura

Publication date: 7 December 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.08.003

zbMATH Keywords

word problemaperiodicfinite monoidomega-termpseudovarietypseudowordregular \(\mathcal{D}\)-class

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70)

Related Items

Reducibility of pointlike problems ⋮ The word problem for omega-terms over the Trotter-Weil hierarchy ⋮ McCammond’s normal forms for free aperiodic semigroups revisited ⋮ The \(\kappa\)-word problem over \(\mathsf{DRH}\) ⋮ Closures of regular languages for profinite topologies. ⋮ The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An automata-theoretic approach to the word problem for \(\omega\)-terms over R
• Description and analysis of a bottom-up DFA minimization algorithm
• REPRESENTATIONS OF THE FREE PROFINITE OBJECT OVER DA
• THE EQUATIONAL THEORY OF ω-TERMS FOR FINITE ${\mathcal R}$-TRIVIAL SEMIGROUPS
• NORMAL FORMS FOR FREE APERIODIC SEMIGROUPS
• A SYNTACTICAL PROOF OF LOCALITY OF DA
• $ℵ_0$-categoricity of linear orderings