Post Correspondence Problem and Small Dimensional Matrices

DOI10.1007/978-3-642-02737-6_3zbMath1247.03089OpenAlexW1536501060MaRDI QIDQ3637212

Tero J.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

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

Cites Work

• Unnamed Item
• When is a pair of matrices mortal?
• Post correspondence problem for short words
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Examples of undecidable problems for 2-generator matrix semigroups
• Decision problems for semi-Thue systems with a few rules
• On Markov's undecidability theorem for integer matrices.
• On undecidability bounds for matrix decision problems
• UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• Mortality of 2 × 2 Matrices
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Developments in Language Theory
• Unsolvability in 3 × 3 Matrices
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• A variant of a recursively unsolvable problem

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