On undecidability bounds for matrix decision problems

DOI10.1016/j.tcs.2007.10.025zbMath1133.03019OpenAlexW2013166518MaRDI QIDQ2474220

Paul C. Bell, Igor Potapov

Publication date: 5 March 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.10.025

zbMATH Keywords

computability theorymatrix semigroupspiecewise linear mapsmembershipvector reachability

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25)

Related Items (11)

Reachability Problems for One-Dimensional Piecewise Affine Maps ⋮ What else is undecidable about loops? ⋮ Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\) ⋮ Reachability problems in quaternion matrix and rotation semigroups ⋮ Weighted automata on infinite words in the context of attacker-defender games ⋮ ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS ⋮ Unnamed Item ⋮ Reachability problems in low-dimensional nondeterministic polynomial maps over integers ⋮ An algebraic view on p-admissible concrete domains for lightweight description logics ⋮ Post Correspondence Problem and Small Dimensional Matrices ⋮ Using model theory to find decidable and tractable description logics with concrete domains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• When is a pair of matrices mortal?
• Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
• Examples of undecidable problems for 2-generator matrix semigroups
• Decision problems for semi-Thue systems with a few rules
• The mortality problem for matrices of low dimensions
• Improved matrix pair undecidability results
• Mortality in Matrix Semigroups
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• Computation in One-Dimensional Piecewise Maps
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Mathematical Foundations of Computer Science 2004
• Unconventional Computation
• REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
• Unsolvability in 3 × 3 Matrices
• Developments in Language Theory

This page was built for publication: On undecidability bounds for matrix decision problems