Geodesic
Context-Freeness of the Languages of Schützenberger Automata of HNN-Extensions of Finite Inverse Semigroups
Publications de l'Institut Mathématique, _N_S_99 (2016) no. 113, p. 177

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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.
DOI : 10.2298/PIM141227016A
Classification : 20M18, 20M35, 68Q45
Keywords: inverse semigroup, Schützenberger automaton, context-free language 
@article{10_2298_PIM141227016A,
     author = {Mohammed Abu Ayyash and Emanuele Rodaro},
     title = {Context-Freeness of the {Languages} of {Sch\"utzenberger} {Automata} of {HNN-Extensions} of {Finite} {Inverse} {Semigroups}},
     journal = {Publications de l'Institut Math\'ematique},
     pages = {177 },
     publisher = {mathdoc},
     volume = {_N_S_99},
     number = {113},
     year = {2016},
     doi = {10.2298/PIM141227016A},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.2298/PIM141227016A/}
}
TY  - JOUR
AU  - Mohammed Abu Ayyash
AU  - Emanuele Rodaro
TI  - Context-Freeness of the Languages of Schützenberger Automata of HNN-Extensions of Finite Inverse Semigroups
JO  - Publications de l'Institut Mathématique
PY  - 2016
SP  - 177 
VL  - _N_S_99
IS  - 113
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.2298/PIM141227016A/
DO  - 10.2298/PIM141227016A
LA  - en
ID  - 10_2298_PIM141227016A
ER  - 
%0 Journal Article
%A Mohammed Abu Ayyash
%A Emanuele Rodaro
%T Context-Freeness of the Languages of Schützenberger Automata of HNN-Extensions of Finite Inverse Semigroups
%J Publications de l'Institut Mathématique
%D 2016
%P 177 
%V _N_S_99
%N 113
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.2298/PIM141227016A/
%R 10.2298/PIM141227016A
%G en
%F 10_2298_PIM141227016A
Mohammed Abu Ayyash; Emanuele Rodaro. Context-Freeness of the Languages of Schützenberger Automata of HNN-Extensions of Finite Inverse Semigroups. Publications de l'Institut Mathématique, _N_S_99 (2016) no. 113, p. 177 . doi: 10.2298/PIM141227016A

Cité par Sources :