HNN-extensions of finite inverse semigroups

The concept of HNN-extensions of groups was introduced by Higman, Neumann and Neumann in 1949. HNN-extensions and amalgamated free products have played a crucial role in combinatorial group theory, especially for algorithmic problems. In inverse semigroup theory there are many ways of constructing HNN-extension in order to ensure the embeddability of the original inverse semigroup in the new one. For instance, Howie used unitary subsemigroups , N.D. Gilbert used ordered ideals and Yamamura put some conditions on idempotents. In this thesis we adopt Yamamura’s definition. Let S* = [S; A,B] be an HNN-extension of inverse semigroups. We show that the word problem of HNN-extensions of inverse semigroups can be undecidable even under some nice conditions on S, A and B. Then we consider HNN-extension S* with S finite , because under such hypothesis the word problem is decidable and we prove that the Schützenberger graph of the elements of S* is a context-free graph, showing that the language recognized by the Schützenberger automaton is a deterministic context-free language. Moreover, we construct the grammar generating this language. We characterize the HNN-extensions of finite inverse semigroups which are completely semisimple inverse semigroups, using a characterization of HNN-extensions of finite inverse semigroups which have a copy of the bicyclic monoid as subsemigroup. Furthermore, we give some properties of the Schützenberger graph of the elements of HNN-extensions of finite inverse semigroups mainly focusing on properties of the hosts, i.e. minimal finite subgraphs that contain all essential information about the automaton. We use the description of such Schützenberger automata and the Bass-Serre theory to study the maximal subgroups of the HNN-extensions of finite inverse semigroups.

Higman, Neumann e Neumann, hanno introdotto nel 1949 la nozione di HNN-estensioni di gruppi , nozione che, insieme a quella di amalgami, ha giocato un ruolo importante nella teoria combinatoria dei gruppi e dato origine ad interessanti problemi algoritmici. Mentre la nozione di amalgami può essere facilmente introdotta per i semigruppi inversi, in quanto ogni amalgama di semigruppi inversi si immerge in un semigruppo inverso, alcune condizioni devono essere imposte sui semigruppi inversi per garantire l’immergibilità del semigruppo originale nella estensione. Questo ha dato luogo a varie possibili definizioni di HNN estensioni, ad esempio Howie ha definito le estensioni per semigruppi unitari, Gilbert ha utilizzato ideali ordinati, Yamamura ha posto alcune condizioni su idempotenti. In questa tesi abbiamo considerato la definizione di Yamamura e denotiato con S*=[S;A,B] una estensione di questo tipo. Abbiamo dimostrato che il problema della parola per S* può essere indecidibile anche se si pongono su S, A e B condizioni che nel caso dei gruppi garantiscono la decidibilità di tale problema. Abbiamo quindi considerato HNN-estensioni di semigruppi finiti (che hanno problema della parola decidibile). Abbiamo provato che, se S è finito, il grafo di Schützenberger degli elementi di S* è un grafo context-free e quindi il linguaggio riconosciuto dagli automi di Schützenberger degli elementi di S* è un linguaggio deterministico libero da contesto. Abbiamo anche costruito una grammatica libera da contesto che riconosce tale linguaggio. Passando poi alla struttura delle HNN-estensioni di semigruppi inversi finiti, abbiamo caratterizzato quelle estensioni che sono un semigruppo inverso completamente semisemplice, determinando le HNN-estensioni di semigruppi inversi finiti che ammettono come sottogruppo una copia del monoide biciclico. Infine abbiamo descritto alcune proprietà di sottografi (host) del grafo di Schützenberger degli elementi di una HNN-estensione di semigruppi inversi finiti che contengono tutte le informazioni essenziali per descrivere il grafo stesso . Utilizzando la teoria di Bass-Serre e le proprietà degli host abbiamo studiato i sottogruppi massimali delle HNN-estensioni di semigruppi inversi finiti.