Reachability Problems for Words and Matrices
- 16:30 30th October 2012 ( week 4, Michaelmas Term 2012 )Lecture Theatre B
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.