An automata-theoretic approach to the word problem for -terms over R

DOI10.1016/J.TCS.2006.10.019MaRDI QIDQ868948zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• THE EQUATIONAL THEORY OF ω-TERMS FOR FINITE ${\mathcal R}$-TRIVIAL SEMIGROUPS
• The word problem for \(\omega \)-terms over DA
• Complete reducibility of systems of equations with respect to \(\mathbf R\).
• The word problem for omega-terms over the Trotter-Weil hierarchy
• McCammond’s normal forms for free aperiodic semigroups revisited

Cites work

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

Cited in

(17)

• Representations of the free profinite object over \(\mathbf{DA}\).
• Towards a pseudoequational proof theory
• The word problem for omega-terms over the Trotter-Weil hierarchy
• Some reducibility properties for pseudovarieties of the form \(DRH\)
• The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
• The \(\kappa\)-word problem over \(\mathsf{DRH}\)
• Pointlike sets with respect to R and J.
• Closures of regular languages for profinite topologies.
• On \(\omega \)-identities over finite aperiodic semigroups with commuting idempotents
• The word problem for \(\omega \)-terms over DA
• Complete κ-reducibility of pseudovarieties of the form DRH
• McCammond’s normal forms for free aperiodic semigroups revisited
• The word problem for -terms over the pseudovariety of local groups
• Recognizing pro-\(\mathrm{R}\) closures of regular languages
• Profinite topologies
• On bases of identities for the -variety generated by locally testable semigroups.
• Tameness of pseudovariety joins involving R.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868948)