Undecidability of the identity problem for finite semigroups

DOI10.2307/2275184zbMath0780.20035OpenAlexW2022794917MaRDI QIDQ4008756

Robert Baldinger, Douglas Albert, 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

relationsTuring machineequationsundecidable word problempseudovariety of finite semigroupsidentity problem

Mathematics Subject Classification ID

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

Related Items

Reducibility of Joins Involving Some Locally Trivial Pseudovarieties, 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, Pointlike sets and separation: a personal perspective, The join of the pseudovarieties of idempotent semigroups and locally trivial semigroups, Tameness of Some Locally Trivial Pseudovarieties, Some reducibility properties for pseudovarieties of the form DRH, Recognizing pro-\(\mathrm{R}\) closures of regular languages, The \(\kappa\)-word problem over \(\mathsf{DRH}\), John Rhodes and the theory of finite semigroups., On the atoms of algebraic lattices arising in 𝔮-theory, Complete κ-reducibility of pseudovarieties of the form DRH, Finite state automata: A geometric approach, TAMENESS OF JOINS INVOLVING THE PSEUDOVARIETY OF LOCAL SEMILATTICES, ON THE DECIDABILITY OF MEMBERSHIP IN THE GLOBAL OF A MONOID PSEUDOVARIETY, The pseudovariety $J$ is hyperdecidable, TAMENESS OF THE PSEUDOVARIETY LS1, Every decidable pseudovariety of abelian groups is completely tame, On Pointlike Sets and Joins of Pseudovarieties, Representations of relatively free profinite semigroups, irreducibility, and order primitivity, COMPLETE REDUCIBILITY OF THE PSEUDOVARIETY LS1, Varieties, Profinite topologies, On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids, On the hyperdecidability of semidirect products of pseudovarieties, On equational theories of classes of finite rings, 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, Tameness of pseudovariety joins involving R.

Cites Work

• Unnamed Item
• Categories as algebra: An essential ingredient in the theory of monoids
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I
• Avoidable patterns in strings of symbols
• The Birkhoff theorem for finite algebras
• The lattice of semigroup varieties
• Identical relations in finite groups
• Unending chess, symbolic dynamics and a problem in semi-groups
• Varieties and simple groups
• Recursive Unsolvability of a problem of Thue