Skip to main content

Reachability Problems for Words and Matrices

Igor Potapov ( University of Liverpool )

Most computational problems for matrix semigroups and groups are inherently difficult to solve and even undecidable starting from dimension three or four. The examples of such problems are the membership problem (including the special cases of the mortality and identity problems), vector reachability, scalar reachability, freeness problems and emptiness of matrix semigroups intersection. Many questions about the decidability and complexity of problems for two-dimensional matrix semigroups remain open and are directly linked with other challenging problems in the field.

In this talk several closely related fundamental problems for words and matrices will be considered. I will survey a number of new techniques and encodings used to solve long standing open problem about reachability of Identity matrix; discuss hardness and decidability results for 2x2 matrix semigroups  as well as highlight interconnections between matrix problems, reachability for iterative maps and combinatorics on words.

Speaker bio

http://cgi.csc.liv.ac.uk/~igor/

Share this: