A Note on the Emptiness of Semigroup Intersections

• Autorzy: Bell P.
• Języki publikacji: EN

Abstrakty

EN

We consider decidability questions for the emptiness problem of intersections of matrix semigroups. This problem was studied by A. Markov [7] and more recently by V. Halava and T. Harju [5]. We give slightly strengthened results of their theorems by using a different matrix encoding. In particular, we show that given two finitely generated semigroups of non-singular upper triangular 3 ×3 matrices over the natural numbers, checking the emptiness of their intersections is undecidable. We also show that the problem is undecidable even for unimodular matrices over 3 ×3 rational matrices.

Słowa kluczowe

EN

matrix semigroups; semigroup intersection; undecidability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 1-2
• Strony: 1--4
• Opis fizyczny: bibliogr. 9 poz.

Twórcy

autor

Bell P.

• Department of Computer Science, The University of Liverpool, Ashton Buiding, Ashton Street, Liverpool, L69 3BX, UK,

Bibliografia

• [1] P. Bell, I. Potapov, On the Membership of Invertible Diagonal Matrices, Theor. Comput. Sci., 372, 2007, 37-45.
• [2] P. Bell, I. Potapov, Reachability Problems in QuaternionMatrix and Rotation Semigroups,Manuscript, 2006.
• [3] J. Cassaigne, T. Harju, J. Karhumäki, On the Decidability of Freeness ofMatrix Semigroups, Internat. Journal of Algebra and Comput., 9, 1999, 295-305.
• [4] V. Claus, Some Remarks on PCP(k) and Related Problems, Bulletin of EATCS, 12, 1980, 54-61.
• [5] V. Halava, T. Harju, On Markov's Undecidability Theorem for Integer Matrices, TUCS Technical Report No. 758, 2006.
• [6] D. Klarner, J. Birget,W. Satterfield, On the Undecidability of the Freeness of Integer Matrix Semigroups, Int. Journal of Algebra Comp, 1, 1991, 223-226.
• [7] A. Markov, On Certain Insoluble Problems Concerning Matrices, Doklady Akad. Nauk SSSR, 57, 1947, 539-542.
• [8] Y. Matiyasevich, G. Sénizergues, Decision Problems for Semi-Thue Systems with a Few Rules,Theoretical Computer Science, 330, No. 1, 2005, 145-169.
• [9] M. Paterson, Unsolvability in 3 × 3 matrices, Studies in Applied Mathematics, 49, 1970, 105-107.