Context-freeness of the languages of Schützenberger automata of HNN-extensions of finite inverse semigroups | Zendy

Mohammed Abu Ayyash | Zendy; Emanuele Rodaro | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Context-freeness of the languages of Schützenberger automata of HNN-extensions of finite inverse semigroups

Author(s) -

Mohammed Abu Ayyash,

Emanuele Rodaro

Publication year - 2015

Publication title -

publications de l institut mathematique

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.246

H-Index - 17

eISSN - 1820-7405

pISSN - 0350-1302

DOI - 10.2298/pim141227016a

Subject(s) - decidability , inverse semigroup , inverse , mathematics , extension (predicate logic) , semigroup , automaton , discrete mathematics , krohn–rhodes theory , computer science , special classes of semigroups , theoretical computer science , programming language , geometry

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research