Undecidability bounds for integer matrices using Claus instances

DOI10.1142/S0129054107005066zbMATH Open1202.03052OpenAlexW2019875210MaRDI QIDQ3065609FDOQ3065609

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

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

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)

Cites Work

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

Cited In (29)

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