You are not logged in | Log in

Decidability problems in infinite semigroups

Ruiwen Dong
Saarland University
Nov. 29, 2023, 2:15 p.m.
room 5050
Seminar Automata Theory

This talk is about several algorithmic problems for matrix semigroups. A classic problem in this area is the well-known Semigroup Membership problem: given as input a finite set of square matrices S = {A1, A2, ... Ak} and a matrix A, decide whether there exists a sequence of matrices from S whose product is equal to A. This problem is highly intractable and has been shown to be undecidable even for integer matrices of dimension four. For this reason, we focus on the special case where the matrix A is restricted the identity matrix. This is called the Identity Problem, and enjoys the property of being decidable for a much larger class of matrices, while remaining undecidable for general matrices. We aim towards a group-theoretic classification of the cases where the Identity Problem is decidable.