Products of matrices and recursively enumerable sets

DOI10.1016/j.jcss.2014.10.004zbMath1401.03080MaRDI QIDQ473201

Juha Honkala

Publication date: 24 November 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.10.004

zbMATH Keywords

decidability; recursively enumerable set; matrix; Rice's theorem; Diophantine representation

Mathematics Subject Classification ID

03D35: Undecidability and degrees of sets of sentences

15A30: Algebraic systems of matrices

03D25: Recursively (computably) enumerable sets and degrees

Related Items

On the Identity Problem for the Special Linear Group and the Heisenberg Group., On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond, On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond, Quasi-universal \(k\)-regular sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the membership of invertible diagonal and scalar matrices
• On finite semigroups of matrices
• The freeness problem over matrix semigroups and bounded languages
• On the decidability of semigroup freeness
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• Polynomial-time algorithm for the orbit problem
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Unsolvability in 3 × 3 Matrices
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS