Undecidability bounds for integer matrices using Claus instances

DOI10.1142/S0129054107005066MaRDI QIDQ3065609zbMATH OpenOpenAlexFDO

Authors Vesa Halava, Tero Harju, Mika Hirvensalo

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

zbMATH Keywords

integer matrices undecidability reachability problem post correspondence problem

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Undecidability and degrees of sets of sentences (03D35)

Recommendations

Improved matrix pair undecidability results
Post Correspondence Problem and Small Dimensional Matrices
On undecidability bounds for matrix decision problems
Lowering Undecidability Bounds for Decision Questions in Matrices
ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS

Cites work

scientific article; zbMATH DE number 3550181 (Why is no real title available?)
A variant of a recursively unsolvable problem
Decision problems for semi-Thue systems with a few rules
Examples of undecidable problems for 2-generator matrix semigroups
Mortality in Matrix Semigroups
Mortality of 2 × 2 Matrices
ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
Some decision problems on integer matrices
Unsolvability in 3 × 3 Matrices
When is a pair of matrices mortal?

Cited in

(29)

On simulating Turing machines with matrix semigroups with integrality tests
On Nonnegative Integer Matrices and Short Killing Words
Reachability problems in low-dimensional nondeterministic polynomial maps over integers
Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
Post Correspondence Problem and Small Dimensional Matrices
On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
Undecidability in matrices over Laurent polynomials.
Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
On the Identity Problem for the Special Linear Group and the Heisenberg Group.
Unique decipherability in formal languages
On Post correspondence problem for letter monotonic languages
On injectivity of quantum finite automata
Remarks concerning the freeness problem over morphism and matrix semigroups.
Weighted automata on infinite words in the context of attacker-defender games
On finite monoids over nonnegative integer matrices and short killing words
On undecidability bounds for matrix decision problems
Reachability problems in quaternion matrix and rotation semigroups
Freeness properties of weighted and probabilistic automata over bounded languages
Lowering Undecidability Bounds for Decision Questions in Matrices
On the decidability and complexity of problems for restricted hierarchical hybrid systems
The invariance problem for matrix semigroups
Products of matrices and recursively enumerable sets
Improved matrix pair undecidability results
Counting vanishing matrix-vector products
On the membership of invertible diagonal and scalar matrices
Acceptance Ambiguity for Quantum Automata
On Reachability Problems for Low-Dimensional Matrix Semigroups
Solving difference equations whose coefficients are not transcendental
On the decidability of semigroup freeness.

This page was built for publication: Undecidability bounds for integer matrices using Claus instances

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