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 , 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.
|Titolo:||Context-freeness of the languages of Schützenberger automata of HNN-extensions of finite inverse semigroups|
|Data di pubblicazione:||2016|
|Appare nelle tipologie:||01.1 Articolo in Rivista|