×

A note on the emptiness of semigroup intersections. (English) Zbl 1128.03034

The author considers a problem studied by A. Markov and V. Halava: decidability questions for the emptiness problem of intersections of matrix semigroups. By using a different matrix encoding he proves that the problem is undecidable for \(3\times 3\) non-negative upper triangular integral non-singular matrices and also for two semigroups generated by unimodular rational matrices in dimension three.

MSC:

03D35 Undecidability and degrees of sets of sentences
20M05 Free semigroups, generators and relations, word problems