Computational problems concerning the orbit of a point under the action of a matrix semigroup arise in several subfields of computer science, including program analysis, complexity theory, quantum computation, and automata theory. In many cases, the focus extends beyond orbits themselves to orbit closures under a suitable topology. Typically, one starts from a semigroup of matrices and a collection of points, and asks questions about the orbit closures of these points under the semigroup action, for example, whether two given orbit closures intersect.
In this talk, I will introduce and motivate several problems involving semigroups and orbit closures, emphasizing their applications in program analysis and recent developments in computational and determinational aspects. On the computational side, we are given a set of matrices and tasked with computing the defining ideal of the algebraic group generated by them. This problem translates to computing the strongest polynomial invariants for loop programs. The determination task, on the other hand, begins with a given ideal and asks whether (and how) it can be represented as an algebraic semigroup or an orbit closure. The "how" question often concerns whether the underlying semigroup can be topologically generated by s matrices for a given s. In the context of program analysis, this corresponds to synthesizing loop programs from a given pattern in a way that satisfies a specific invariant.
The talk is based on several joint works, (going to be) appeared in POPL, ISSAC and SODA: