Let S be the amalgamated free product of two finite inverse semigroups. We prove that the Schützenberger graph of an element of S with respect to a standard presentation of S is a context-free graph in the sense of Müller and Schupp (Theor. Comput. Sci. 37:51-75, 1985), showing that the language L recognized by the Schützenberger automaton is context-free. Moreover we construct the grammar generating L proving that L is a deterministic context-free language and we use this fact for solving some algorithmic problems.

Amalgams of finite inverse semigroups and deterministic context-free languages

CHERUBINI, ALESSANDRA;NUCCIO, CLAUDIA;RODARO, EMANUELE
2012-01-01

Abstract

Let S be the amalgamated free product of two finite inverse semigroups. We prove that the Schützenberger graph of an element of S with respect to a standard presentation of S is a context-free graph in the sense of Müller and Schupp (Theor. Comput. Sci. 37:51-75, 1985), showing that the language L recognized by the Schützenberger automaton is context-free. Moreover we construct the grammar generating L proving that L is a deterministic context-free language and we use this fact for solving some algorithmic problems.
2012
Amalgam of inverse semigroups; Context free graph; Context-free language; Inverse semigroups; Schützenberger automaton
File in questo prodotto:
File Dimensione Formato  
AMalgams and CF.pdf

Accesso riservato

Descrizione: Articolo principale
: Publisher’s version
Dimensione 604.74 kB
Formato Adobe PDF
604.74 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/664374
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact