Schutzenberger automata for HNN-extensions of inverse semigroups and their use in algorithmic problems

In our talk we will review some of the combinatorial methods in inverse semigroup theory. We use Sch\" utzenberger automata that are instrumental~-~as shown by the combinatorial approach introduced by Munn and extended by Stephen~-~in the study of structural and algorithmic questions for inverse semigroup presentations.

HNN extensions, first introduced for groups, where they play an important role in applications to algorithmic problems, proved useful in the study of decidability questions also in the class of inverse semigroups.We study HNN-extensions of inverse semigroups via structure of their Sch\" utzenberger automata.

We will characterize Sch\" utzenberger automata for a class of lower bounded HNN-extensions. Based on our recent results with Paul Bennett, I will argue that this is a rather rich and important class of HNN-extensions. The automata contain a special subgraph~-~a core~-~with finitely many lobes from which all vital information about the automata can be retrieved. This gives us in some cases an effective construction of the Sch\" utzenberger automaton and thus provides a solution for the word problem.

Date and Venue

Start Date
Online Zoom meeting
End Date


Tatiana Jajcayova

Speaker's Institution

Department of Applied Informatics, Comenius University, Bratislava, Slovakia



Semigroups, Automata and Languages