Improved matrix pair undecidability results

DOI10.1007/S00236-007-0047-YMaRDI QIDQ2641877zbMATH OpenOpenAlexFDO

Authors Vesa Halava, Mika Hirvensalo

Publication date 17 August 2007

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-007-0047-y

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• On undecidability bounds for matrix decision problems
• Lowering Undecidability Bounds for Decision Questions in Matrices
• Undecidability bounds for integer matrices using Claus instances
• scientific article; zbMATH DE number 2087212
• On Markov's undecidability theorem for integer matrices.

Cites work

• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• A variant of a recursively unsolvable problem
• Compactness of Systems of Equations in Semigroups
• Decision problems for semi-Thue systems with a few rules
• Examples of undecidable problems for 2-generator matrix semigroups
• Lowering Undecidability Bounds for Decision Questions in Matrices
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• On Computable Numbers, with an Application to the Entscheidungsproblem
• REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
• Undecidability bounds for integer matrices using Claus instances
• Unsolvability in 3 × 3 Matrices
• When is a pair of matrices mortal?

Cited in

(7)

• Reachability problems in low-dimensional nondeterministic polynomial maps over integers
• On undecidability bounds for matrix decision problems
• The continuous Skolem-Pisot problem
• Lowering Undecidability Bounds for Decision Questions in Matrices
• Undecidability bounds for integer matrices using Claus instances
• scientific article; zbMATH DE number 2087212 (Why is no real title available?)
• On Reachability Problems for Low-Dimensional Matrix Semigroups

This page was built for publication: Improved matrix pair undecidability results

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