A Note on the Emptiness of Semigroup Intersections

Article type: Research Article

Authors: Bell, Paul

Affiliations: Department of Computer Science, The University of Liverpool, Ashton Building, Ashton Street, Liverpool, L69 3BX, UK. E-mail: [email protected]

Abstract: 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.

Keywords: Matrix Semigroups, Semigroup Intersection, Undecidability

Journal: Fundamenta Informaticae, vol. 79, no. 1-2, pp. 1-4, 2007