## Пятница 26 октября, 17-00, ауд. 203

Пятница, 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 to integer matrices implies a lot of undecidability results on 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 to integer matrices, and consequently there are no analogous undecidability results for matrices. On the contrary, many problems known undecidable can be shown decidable for 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 matrices are NP-hard. (Joint work with Paul Bell and Igor Potapov)