Пятница, 25 октября, ауд. 203. Начало в 15:15.
Докладчик: Mika Hirvensalo (University of Turku).
Тема: On the computational complexity of two-dimensional integer matrix problems.
Abstract
Embedding the Cartesian product of two free semigroups into 3 times 3 integer matrices is a well known technique at least since 1970's. The said embedding implies that word pairs can be encoded in 3 times 3 integer matrices, which in turn implies the existence of undecidable 3 times 3 integer matrix problems. Similar embedding into 2 times 2 matrices is impossible, and undecidability results for those matrices cannot be established that way. Quite on the contrary, it can be shown that many problems undecidable for higher dimensions are indeed decidable for 2 times 2 matrices, at least with some restrictions. In this presentation, we outline the decision procedure and present complexity lower and upper bounds for some particular 2 times 2 matrix problems.
