CONTEXT-FREENESS OF THE LANGUAGES OF SCHÜTZENBERGER AUTOMATA OF HNN-EXTENSIONS OF FINITE INVERSE SEMIGROUPS

Mohammed Abu Ayyash, Emanuele Rodaro

Abstract: We prove that the Schützenberger graph of any element of the HNN-extension of a finite inverse semigroup $S$ with respect to its standard presentation is a context-free graph in the sense of [11], showing that the language $L$ recognized by this automaton is context-free. Finally we explicitly construct the grammar generating $L$, and from this fact we show that the word problem for an HNN-extension of a finite inverse semigroup $S$ is decidable and lies in the complexity class of polynomial time problems.

Keywords: inverse semigroup; Schützenberger automaton; context-free language

Classification (MSC2000): 20M18; 20M35; 68Q45

Full text of the article: (for faster download, first choose a mirror)

• Compressed DVI file (40 kilobytes)
• Compressed PostScript file (428 kilobytes)
• PDF file (204 kilobytes)