Пятница, 26 октября, ауд. 203. Начало в 17:00.
Докладчик: Mika Hirvensalo (University of Turku).
Тема: Undecidability and complexity issues on integer matrices.
Abstract
For a finite alphabet A, a well known embedding
![$ A^* \times A^* $](/sites/default/files/tex/4304546ddf01f21358965a15507cb83d74334ae1.png)
to
![$ 3 \times 3 $](/sites/default/files/tex/5968ffddb06995e676822a22e6512e0670845a0a.png)
integer matrices implies a lot of undecidability results on
![$ 3 \times 3 $](/sites/default/files/tex/5968ffddb06995e676822a22e6512e0670845a0a.png)
integer matrices. Various constructions allow to establish the undecidability on a small number of matrices, even though the size of matrices has to be increased.
On the other hand, we cannot construct an embedding
![$ A^* \times A^* $](/sites/default/files/tex/4304546ddf01f21358965a15507cb83d74334ae1.png)
to
![$ 2 \times 2 $](/sites/default/files/tex/3bbb9dbc124192ff2a0f88928f4cc695792fc3c8.png)
integer matrices, and consequently there are no analogous undecidability results for
![$ 2 \times 2 $](/sites/default/files/tex/3bbb9dbc124192ff2a0f88928f4cc695792fc3c8.png)
matrices. On the contrary, many problems known undecidable can be shown decidable for
![$ 2 \times 2 $](/sites/default/files/tex/3bbb9dbc124192ff2a0f88928f4cc695792fc3c8.png)
integer matrices. However, the complexities of such problems are not studied very well. It can be shown that the identity problem and the mortality problem for
![$ 2 \times 2 $](/sites/default/files/tex/3bbb9dbc124192ff2a0f88928f4cc695792fc3c8.png)
matrices are NP-hard. (Joint work with Paul Bell and Igor Potapov)