Products of matrices and recursively enumerable sets

DOI10.1016/J.JCSS.2014.10.004zbMATH Open1401.03080OpenAlexW2011410600MaRDI QIDQ473201FDOQ473201

Authors 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

matrixdecidabilityRice's theoremDiophantine representationrecursively enumerable set

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Algebraic systems of matrices (15A30) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• scientific article; zbMATH DE number 1848277
• On characterizations of recursively enumerable languages
• On Markov's undecidability theorem for integer matrices.
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Undecidability in matrices over Laurent polynomials.

Cites work

• scientific article; zbMATH DE number 3902039 (Why is no real title available?)
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 42574 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• On finite semigroups of matrices
• On the decidability of semigroup freeness.
• On the membership of invertible diagonal and scalar matrices
• Polynomial-time algorithm for the orbit problem
• The freeness problem over matrix semigroups and bounded languages
• Undecidability bounds for integer matrices using Claus instances
• Unsolvability in 3 × 3 Matrices

Cited in

(7)

• 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
• On the Identity Problem for the Special Linear Group and the Heisenberg Group.
• Quasi-universal \(k\)-regular sequences
• scientific article; zbMATH DE number 6831954 (Why is no real title available?)
• Generalized recurrence and the nonwandering set for products
• scientific article; zbMATH DE number 1848277 (Why is no real title available?)

This page was built for publication: Products of matrices and recursively enumerable sets

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