Armin Weiß is a researcher at the University of Stuttgart, focusing on complexity theory and algorithmic problems in group theory. He earned his PhD and Habilitation at the same university, where his research has addressed the complexity of group-theoretic problems, such as the conjugacy and word problems in various groups, in particular, in amalgamated products and HNN extensions. His work explores the computational aspects of group theory, including context-free groups and equations of solvable groups under the exponential time hypothesis. Armin's interests also extend to other algorithms such as in the area of sorting.

AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

60 Minutes

Kaiserslautern

The DFA intersection emptiness problem is a well-known PSPACE-complete problem. A closely related, but more algebraic, problem is the subsemigroup membership problem for transformation semigroups acting on the states of the automata. A natural question arises: for which classes of semigroups does the membership problem remain PSPACE-complete, and for which can it be solved efficiently? One particularly interesting class of semigroups are inverse semigroups, which can be represented as semigroups of partial bijections on a set and serve as an intermediate class between groups and arbitrary semigroups.

In this talk, I will survey recent advancements in the complexity of the membership and also conjugacy problems, with a special focus on inverse semigroups. Specifically, for varieties of inverse semigroups, we provide a complete and unconditional characterization of when these problems are PSPACE-complete and when they are not. We also solve the problem when the inverse semigroup is given by its multiplication table.

This talk is based on ongoing joint work with Lukas Fleischer, Florian Stober, and Alexander Thumm.


Please contact the office team for link information

Geraldine Anderson

+49 631 9303 9607

--email hidden

passcode not visible

logged in users only