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

DOI10.1016/J.TCS.2006.10.019zbMATH Open1110.68059OpenAlexW1996599450MaRDI QIDQ868948FDOQ868948

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

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

zbMATH Keywords

semigroupword problemautomata minimizationomega-termpseudovarietypseudowordidentity basis

Mathematics Subject Classification ID

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

Cites Work

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

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
• Pointlike sets with respect to R and J.
• The \(\kappa\)-word problem over \(\mathsf{DRH}\)
• On \(\omega \)-identities over finite aperiodic semigroups with commuting idempotents
• Closures of regular languages for profinite topologies.
• 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 \(\kappa \)-terms over the pseudovariety of local groups
• Recognizing pro-\(\mathrm{R}\) closures of regular languages
• Profinite topologies
• On bases of identities for the \(\omega\)-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)