An automata-theoretic approach to the word problem for \(\omega\)-terms over R

DOI10.1016/j.tcs.2006.10.019zbMath1110.68059OpenAlexW1996599450MaRDI QIDQ868948

Marc Zeitoun, Jorge Almeida

Publication date: 26 February 2007

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

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

zbMATH Keywords

semigroupword problemautomata minimizationomega-termpseudovarietypseudowordidentity basis

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (17)

The word problem for omega-terms over the Trotter-Weil hierarchy ⋮ Some reducibility properties for pseudovarieties of the form DRH ⋮ Recognizing pro-\(\mathrm{R}\) closures of regular languages ⋮ McCammond’s normal forms for free aperiodic semigroups revisited ⋮ The \(\kappa\)-word problem over \(\mathsf{DRH}\) ⋮ The word problem for \(\omega \)-terms over DA ⋮ Complete κ-reducibility of pseudovarieties of the form DRH ⋮ Closures of regular languages for profinite topologies. ⋮ Towards a pseudoequational proof theory ⋮ On bases of identities for the \(\omega\)-variety generated by locally testable semigroups. ⋮ Pointlike sets with respect to R and J. ⋮ The word problem for \(\kappa \)-terms over the pseudovariety of local groups ⋮ The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy ⋮ REPRESENTATIONS OF THE FREE PROFINITE OBJECT OVER DA ⋮ Profinite topologies ⋮ On $$\omega $$-Identities over Finite Aperiodic Semigroups with Commuting Idempotents ⋮ Tameness of pseudovariety joins involving R.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tameness of pseudovariety joins involving R.
• Lexicographically least circular substrings
• The Birkhoff theorem for finite algebras
• Minimisation of acyclic deterministic automata in linear time
• The join of the pseudovarieties of \(\mathcal R\)-trivial and \(\mathcal L\)-trivial monoids
• Re-describing an algorithm by Hopcroft
• THE EQUATIONAL THEORY OF ω-TERMS FOR FINITE ${\mathcal R}$-TRIVIAL SEMIGROUPS
• Fast canonization of circular strings
• Defining Relations and the Algebraic Structure of the Group SL₂ over Integral Hamilton Quaternions
• On the Decidability of Iterated Semidirect Products with Applications to Complexity
• POINTLIKE SETS, HYPERDECIDABILITY AND THE IDENTITY PROBLEM FOR FINITE SEMIGROUPS
• A SYNTACTICAL PROOF OF LOCALITY OF DA
• Depth-First Search and Linear Graph Algorithms
• Long words: The theory of concatenation and \(\omega\)-power

This page was built for publication: An automata-theoretic approach to the word problem for \(\omega\)-terms over R