Publications de l'Institut Mathématique, Nouvelle Série Vol. 99(113), pp. 177–191 (2016) 

CONTEXTFREENESS OF THE LANGUAGES OF SCHÜTZENBERGER AUTOMATA OF HNNEXTENSIONS OF FINITE INVERSE SEMIGROUPSMohammed Abu Ayyash, Emanuele RodaroDepartment of Mathematics, Politecnico di Milano "F. Brioschi", Milan, Italy; Centro de Matematica, Universidade do Porto, Porto, PortugalAbstract: We prove that the Schützenberger graph of any element of the HNNextension of a finite inverse semigroup $S$ with respect to its standard presentation is a contextfree graph in the sense of [11], showing that the language $L$ recognized by this automaton is contextfree. Finally we explicitly construct the grammar generating $L$, and from this fact we show that the word problem for an HNNextension of a finite inverse semigroup $S$ is decidable and lies in the complexity class of polynomial time problems. Keywords: inverse semigroup; Schützenberger automaton; contextfree language Classification (MSC2000): 20M18; 20M35; 68Q45 Full text of the article: (for faster download, first choose a mirror)
Electronic fulltext finalized on: 12 Apr 2016. This page was last modified: 20 Apr 2016.
© 2016 Mathematical Institute of the Serbian Academy of Science and Arts
