On Markov's undecidability theorem for integer matrices.

DOI10.1007/S00233-007-0714-XMaRDI QIDQ2460065zbMATH OpenOpenAlexFDO

Authors Vesa Halava, Tero Harju

Publication date 14 November 2007

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00233-007-0714-x

zbMATH Keywords

decidabilityfinitely generated matrix semigroups

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Algebraic systems of matrices (15A30) Free semigroups, generators and relations, word problems (20M05) Word problems, etc. in computability and recursion theory (03D40)

Recommendations

• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Examples of undecidable problems for 2-generator matrix semigroups
• scientific article; zbMATH DE number 2087212
• A note on the emptiness of semigroup intersections
• Some decision problems on integer matrices

Cited in

(12)

• On factorizations of upper triangular nonnegative matrices of order three
• Post Correspondence Problem and Small Dimensional Matrices
• Undecidability in matrices over Laurent polynomials.
• A note on the emptiness of semigroup intersections
• On undecidability bounds for matrix decision problems
• On upper triangular nonnegative matrices.
• Reachability problems in quaternion matrix and rotation semigroups
• Products of matrices and recursively enumerable sets
• Number theory of matrix semigroups
• Improved matrix pair undecidability results
• Semigroup intersection problems in the Heisenberg groups
• scientific article; zbMATH DE number 2087212 (Why is no real title available?)

This page was built for publication: On Markov's undecidability theorem for integer matrices.

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