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

Word problems, etc. in computability and recursion theory (03D40) Algebraic systems of matrices (15A30) 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
• 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

(15)

• Examples of undecidable problems for 2-generator matrix semigroups
• On factorizations of upper triangular nonnegative matrices of order three
• On undecidability bounds for matrix decision problems
• Improved matrix pair undecidability results
• Post Correspondence Problem and Small Dimensional Matrices
• Products of matrices and recursively enumerable sets
• scientific article; zbMATH DE number 2087212 (Why is no real title available?)
• On upper triangular nonnegative matrices.
• A note on the emptiness of semigroup intersections
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Number theory of matrix semigroups
• Semigroup intersection problems in the Heisenberg groups
• Undecidability in matrices over Laurent polynomials.
• Probabilistic finite automaton emptiness is undecidable for a fixed automaton
• Reachability problems in quaternion matrix and rotation semigroups

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)