The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups

DOI10.1142/S0218196722500540MaRDI QIDQ5097713zbMATH OpenOpenAlexFDO

Authors J.-C. Birget, Alexey Talambutsa

Publication date 31 August 2022

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.02408

zbMATH Keywords

freeness problem for integer matrix semigroups and for subsemigroups of the direct product of free groupssymmetric Post correspondence problem

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Undecidability and degrees of sets of sentences (03D35) Free semigroups, generators and relations, word problems (20M05) Semigroups of transformations, relations, partitions, etc. (20M20)

Recommendations

• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Remarks concerning the freeness problem over morphism and matrix semigroups.
• The freeness problem over matrix semigroups and bounded languages
• On the decidability of semigroup freeness.

Cites work

• A variant of a recursively unsolvable problem
• scientific article; zbMATH DE number 3909745 (Why is no real title available?)
• scientific article; zbMATH DE number 3211077 (Why is no real title available?)
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Recursive unsolvability of a problem of Thue

Cited in

(5)

• The Post correspondence problem in groups.
• Periodic and Infinite Traces in Matrix Semigroups
• Developments in Language Theory
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Post's Correspondence Problem for hyperbolic and virtually nilpotent groups

This page was built for publication: The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups

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