Algorithmic problems for amalgams of finite semigroups
It is proved that there is an amalgam of two finite semigroups such that the corresponding amalgamated product has an undecidable word problem. Further, both the problems of embeddability of finite semigroup amalgams in arbitrary semigroups and into finite semigroups are undecidable. Moreover, the finite semigroups involved can be taken to have the property that all products of length four equal zero. The proofs use several versions of Minsky algorithms (one type of which consists of a numbered sequence of instructions for passing coins between two glasses) and a result of Slobodskoj's about undecidability of the universal theory of finite groups. The reader should note that the article was reprinted because of a typesetting error in the original which caused referencing to be omitted: the complete version is in ibid. 232, 767-785 (2000).
- Algorithmic problems for finite groups and finite \(0\)-simple semigroups
- ALGORITHMIC PROBLEMS IN VARIETIES
- Amalgamated Products of Semigroups: The Embedding Problem
- Amalgamation and Inverse and Regular Semigroups
- Epimorphisms and amalgams
- Finite and infinite cyclic extensions of free groups
- scientific article; zbMATH DE number 3179521 (Why is no real title available?)
- scientific article; zbMATH DE number 32084 (Why is no real title available?)
- scientific article; zbMATH DE number 3574107 (Why is no real title available?)
- scientific article; zbMATH DE number 1182704 (Why is no real title available?)
- scientific article; zbMATH DE number 789816 (Why is no real title available?)
- scientific article; zbMATH DE number 3065870 (Why is no real title available?)
- ON THE WORD PROBLEM FOR TENSOR PRODUCTS AND AMALGAMS OF MONOIDS
- ON THE WORD PROBLEM IN PERIODIC GROUP VARIETIES
- Potential Divisibility in Finite Semigroups is Undecidable
- The class of embeddable semigroup amalgams is not finitely axiomatizable
- The Potential -Relation and Amalgamation Bases for Finite Semigroups
- The Word Problem for Abstract Algebras
- Unsolvability of the universal theory of finite groups
- Undecidable problems for completely 0-simple semigroups.
- Concrete algorithms for word problem and subsemigroup problem for semigroups which are disjoint unions of finitely many copies of the free monogenic semigroup
- Amalgams of finite inverse semigroups.
- Normal forms for semigroup amalgams
- Amalgams of inverse semigroups and reversible two-counter machines.
- Semigroups of RN-algorithms
- Minsky Machines and Algorithmic Problems
- Decidability versus undecidability of the word problem in amalgams of inverse semigroups.
- scientific article; zbMATH DE number 1560312 (Why is no real title available?)
- scientific article; zbMATH DE number 1563405 (Why is no real title available?)
- Finitely presented nilsemigroups: complexes with the property of uniform ellipticity
- On the Universal Theory of Torsion and Lacunary Hyperbolic Groups
- ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS
- A semigroup of paths on a sequence of uniformly elliptic complexes
- Amalgams of free inverse semigroups.
- Minimal signatures with undecidability of representability by binary relations
- Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups.
This page was built for publication: Algorithmic problems for amalgams of finite semigroups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1579152)
