No Access

UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES

VESA HALAVA

Department of Mathematics and TUCS – Turku Centre for Computer Science, University of Turku, FIN-20014 Turku, Finland

Corresponding author. Supported by the Academy of Finland under grant 208414.

Search for more papers by this author

TERO HARJU

Department of Mathematics and TUCS – Turku Centre for Computer Science, University of Turku, FIN-20014 Turku, Finland

Search for more papers by this author

, and

MIKA HIRVENSALO

Department of Mathematics and TUCS – Turku Centre for Computer Science, University of Turku, FIN-20014 Turku, Finland

Supported by the Academy of Finland under grant 208797.

Search for more papers by this author

https://doi.org/10.1142/S0129054107005066Cited by:30 (Source: Crossref)

Abstract

There are several known undecidable problems for 3 × 3 integer matrices the proof of which use a reduction from the Post Correspondence Problem (PCP). We establish new lower bounds in the number of matrices for the mortality, zero in the left upper corner, vector reachability, matrix reachability, scalar reachability and freeness problems. Also, we give a short proof for a strengthened result due to Bell and Potapov stating that the membership problem is undecidable for finitely generated matrix semigroups R ⊆ ℤ^4×4 whether or not kI₄ ∈ R for any given |k| > 1. These bounds are obtained by using the Claus instances of the PCP.

Keywords:

References

P. Bell and I. Potapov, On the membership of invertible diagonal matrices, DLT'05, Lecture Notes in Comput. Sci. 3572 (2005) pp. 146–157. Google Scholar
P. Bell and I. Potapov, Lowering Undecidability Bounds for Decision Questions in Matrices, DLT'06, Lecture Notes in Comput. Sci. 4036 (2006) pp. 375–385. Google Scholar
P. Bell and I. Potapov, On undecidability bounds for matrix decision problems, manuscript . Google Scholar
V. D. Blondel and J. N. Tsitsiklis, Information Processing Lett. 63, 283 (1997), DOI: 10.1016/S0020-0190(97)00123-3. Crossref, Web of Science, Google Scholar
J. Cassaigne, T. Harju and J. Karhumäki, Internat. J. Algebra Comput. 9, 295 (1999), DOI: 10.1142/S0218196799000199. Link, Web of Science, Google Scholar
J. Cassaigne and J. Karhumäki, Theoret. Comput. Sci. 204, 29 (1998), DOI: 10.1016/S0304-3975(98)00029-2. Crossref, Web of Science, Google Scholar
C. Choffrut and J. Karhumäki, Theor. Inform. Appl. 39(1), 125 (2005), DOI: 10.1051/ita:2005007. Crossref, Web of Science, Google Scholar
V. Claus, Bull. of the EATCS 12, 54 (1980). Google Scholar
S. Gaubert and R. Katz, Internat. J. Algebra Comp. 16(3), 603 (2006), DOI: 10.1142/S021819670600313X. Link, Web of Science, Google Scholar
V. Halava and T. Harju, Amer. Math. Monthly 108, 649 (2001), DOI: 10.2307/2695274. Crossref, Web of Science, Google Scholar
V. Halava and T. Harju, On Markov's Undecidability Theorem for Integer Matrices, TUCS Tech. Report 758 (2006), submitted . Google Scholar
T. Harju and J. Karhumäki, Handbook of Formal Languages 1, eds. G. Rozenberg and A. Salomaa (Springer-Verlag, 1997) pp. 439–510. Crossref, Google Scholar
D. A. Klarner, J.-C. Birget and W. Satterfield, Internat. J. Algebra Comp. 1, 223 (1991), DOI: 10.1142/S0218196791000146. Link, Google Scholar
R. C. Lyndon and P. E. Schupp , Combinatorial group theory ( Springer-Verlag , 1977 ) . Crossref, Google Scholar
A. Markov, Doklady Akad. Nauk SSSR (N. S.) 57, 539 (1947). Google Scholar
Z. Manna , Mathematical Theory of Computations ( McGraw-Hill , 1974 ) . Google Scholar
Y. Matiyasevich and G. Sénizergues, Theoret. Comput. Sci. 330, 145 (2005), DOI: 10.1016/j.tcs.2004.09.016. Crossref, Web of Science, Google Scholar
M. S. Paterson, Stud. Appl. Math. 49, 105 (1970). Crossref, Web of Science, Google Scholar
E. Post, Bull. Amer. Math. Soc. 52, 264 (1946), DOI: 10.1090/S0002-9904-1946-08555-9. Crossref, Web of Science, Google Scholar
P. Schultz, Amer. Math. Monthly 84, 463 (1977), DOI: 10.2307/2321906. Crossref, Web of Science, Google Scholar