Post Correspondence Problem and Small Dimensional Matrices



: Harju T

: 2009

Lecture Notes in Computer Science

DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS

: LECT NOTES COMPUT SC

: 5583

: 39

: 46

: 8

: 978-3-642-02736-9

: 0302-9743


This is a survey on some undecidable problems on integer matrices. The proofs of these results employ special instances, called Claus instances, of the Post Correspondence Problem. The presentation is based on the article Halava et al. "Undecidability bounds for integer matrices using Claus instances" (Internat. J. Foundations of Comput. Sci. 18, 2007, 931-948).



Last updated on 2025-14-10 at 10:14