Post Correspondence Problem and Small Dimensional Matrices

DOI10.1007/978-3-642-02737-6_3MaRDI QIDQ3637212zbMATH OpenOpenAlexFDO

Authors Tero Harju

Publication date 7 July 2009

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02737-6_3

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Undecidability bounds for integer matrices using Claus instances
• scientific article; zbMATH DE number 2087212
• Undecidability of infinite post correspondence problem for instances of Size 9
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Post correspondence problem for short words

Cites work

• A variant of a recursively unsolvable problem
• Decision problems for semi-Thue systems with a few rules
• Developments in Language Theory
• Examples of undecidable problems for 2-generator matrix semigroups
• scientific article; zbMATH DE number 3730118 (Why is no real title available?)
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• Mortality of 2 × 2 Matrices
• On Markov's undecidability theorem for integer matrices.
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• On undecidability bounds for matrix decision problems
• Post correspondence problem for short words
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Undecidability bounds for integer matrices using Claus instances
• Unsolvability in 3 × 3 Matrices
• When is a pair of matrices mortal?

Cited in

(3)

• Undecidability bounds for integer matrices using Claus instances
• On the identity and group problems for complex Heisenberg matrices
• Decidability of membership problems for flat rational subsets of \(\mathrm{GL}(2,\mathbb{Q})\) and singular matrices

This page was built for publication: Post Correspondence Problem and Small Dimensional Matrices

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