UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
From MaRDI portal
Publication:3065609
DOI10.1142/S0129054107005066zbMath1202.03052OpenAlexW2019875210MaRDI QIDQ3065609
Mika Hirvensalo, Tero J.Harju, Vesa Halava
Publication date: 6 January 2011
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054107005066
Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25)
Related Items (25)
Remarks concerning the freeness problem over morphism and matrix semigroups. ⋮ On the decidability of semigroup freeness ⋮ Improved matrix pair undecidability results ⋮ On the decidability and complexity of problems for restricted hierarchical hybrid systems ⋮ On the membership of invertible diagonal and scalar matrices ⋮ Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ Products of matrices and recursively enumerable sets ⋮ Solving difference equations whose coefficients are not transcendental ⋮ On injectivity of quantum finite automata ⋮ On the Identity Problem for the Special Linear Group and the Heisenberg Group. ⋮ Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\) ⋮ On undecidability bounds for matrix decision problems ⋮ Reachability problems in quaternion matrix and rotation semigroups ⋮ Weighted automata on infinite words in the context of attacker-defender games ⋮ On Post correspondence problem for letter monotonic languages ⋮ Freeness properties of weighted and probabilistic automata over bounded languages ⋮ Unique decipherability in formal languages ⋮ ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS ⋮ The Invariance Problem for Matrix Semigroups ⋮ Reachability problems in low-dimensional nondeterministic polynomial maps over integers ⋮ Post Correspondence Problem and Small Dimensional Matrices ⋮ On finite monoids over nonnegative integer matrices and short killing words ⋮ On Reachability Problems for Low-Dimensional Matrix Semigroups ⋮ Acceptance Ambiguity for Quantum Automata ⋮ On Nonnegative Integer Matrices and Short Killing Words
Cites Work
- When is a pair of matrices mortal?
- Examples of undecidable problems for 2-generator matrix semigroups
- Decision problems for semi-Thue systems with a few rules
- Mortality in Matrix Semigroups
- Mortality of 2 × 2 Matrices
- ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
- Some decision problems on integer matrices
- REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
- Unsolvability in 3 × 3 Matrices
- ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
- A variant of a recursively unsolvable problem
- Unnamed Item
This page was built for publication: UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
