Undecidability of the identity problem for finite semigroups

DOI10.2307/2275184MaRDI QIDQ4008756zbMATH OpenOpenAlexFDO

Authors Douglas Albert, Robert Baldinger, John L. Rhodes

Publication date 27 September 1992

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275184

zbMATH Keywords

equationsidentity problempseudovariety of finite semigroupsrelationsTuring machineundecidable word problem

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Quasivarieties (08C15) Free semigroups, generators and relations, word problems (20M05) Varieties and pseudovarieties of semigroups (20M07)

Recommendations

• scientific article; zbMATH DE number 4008680
• scientific article; zbMATH DE number 1972777
• scientific article; zbMATH DE number 1868880
• On the equational theories of semigroup varieties
• On the membership problem for pseudovarieties of commutative semigroups
• On locally finite varieties with undecidable equational theory.
• scientific article; zbMATH DE number 3287732
• The uniform word problem for groups and finite Rees quotients of \(E\)-unitary inverse semigroups
• The word problem for semigroups presented by a single relation A;\;a=bua.
• scientific article; zbMATH DE number 798167

Cites work

• Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I
• Avoidable patterns in strings of symbols
• Categories as algebra: An essential ingredient in the theory of monoids
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Identical relations in finite groups
• Recursive unsolvability of a problem of Thue
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The Birkhoff theorem for finite algebras
• The lattice of semigroup varieties
• Unending chess, symbolic dynamics and a problem in semi-groups
• Varieties and simple groups

Cited in

(41)

• On equational theories of classes of finite rings
• The \(\kappa\)-word problem over \(\mathsf{DRH}\)
• The join of the pseudovarieties of idempotent semigroups and locally trivial semigroups
• Every decidable pseudovariety of abelian groups is completely tame
• Varieties
• Profinite topologies
• Recognizing pro-\(\mathrm{R}\) closures of regular languages
• John Rhodes and the theory of finite semigroups.
• Finite state automata: a geometric approach
• UNDECIDABILITY AND THE DEVELOPABILITY OF PERMUTOIDS AND RIGID PSEUDOGROUPS
• On the atoms of algebraic lattices arising in 𝔮-theory
• Complete κ-reducibility of pseudovarieties of the form DRH
• On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids
• Reducibility of Joins Involving Some Locally Trivial Pseudovarieties
• Minimal undecidable identity problem for finite-automaton mappings
• On the decidability of membership in the global of a monoid pseudovariety.
• COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1
• On the hyperdecidability of semidirect products of pseudovarieties
• Some undecidable embedding problems for finite semigroups
• The pseudovariety J is hyperdecidable
• scientific article; zbMATH DE number 1944134 (Why is no real title available?)
• PSEUDOVARIETY JOINS INVOLVING ${\mathscr J}$ -TRIVIAL SEMIGROUPS
• HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
• POINTLIKE SETS, HYPERDECIDABILITY AND THE IDENTITY PROBLEM FOR FINITE SEMIGROUPS
• UNDECIDABILITY, AUTOMATA, AND PSEUDOVARITIES OF FINITE SEMIGROUPS
• Some reducibility properties for pseudovarieties of the form DRH
• TAMENESS OF THE PSEUDOVARIETY LS1
• On Pointlike Sets and Joins of Pseudovarieties
• Potential Divisibility in Finite Semigroups is Undecidable
• ON HYPERDECIDABLE PSEUDOVARIETIES OF SIMPLE SEMIGROUPS
• INEVITABLE GRAPHS AND PROFINITE TOPOLOGIES: SOME SOLUTIONS TO ALGORITHMIC PROBLEMS IN MONOID AND AUTOMATA THEORY, STEMMING FROM GROUP THEORY
• PROFINITE METHODS IN SEMIGROUP THEORY
• Tameness of Some Locally Trivial Pseudovarieties
• scientific article; zbMATH DE number 804141 (Why is no real title available?)
• Tameness of joins involving the pseudovariety of local semilattices.
• Representations of relatively free profinite semigroups, irreducibility, and order primitivity
• scientific article; zbMATH DE number 3287732 (Why is no real title available?)
• Closing star-free closure
• Pseudovarieties of semigroups
• Tameness of pseudovariety joins involving R.
• Pointlike sets and separation: a personal perspective

This page was built for publication: Undecidability of the identity problem for finite semigroups

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