We prove that the word problem is decidable in Yamamura’s HNN extensions of finite inverse semigroups, by providing an iterative construction of approximate automata of the Schützenberger automata of words relative to the standard presentation of Yamamura’s HNN-extensions.

Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups

RODARO, EMANUELE;CHERUBINI, ALESSANDRA
2008

Abstract

We prove that the word problem is decidable in Yamamura’s HNN extensions of finite inverse semigroups, by providing an iterative construction of approximate automata of the Schützenberger automata of words relative to the standard presentation of Yamamura’s HNN-extensions.
Inverse semigroup; word problem; Schutzenberger automaton; HNN-extension.
File in questo prodotto:
File Dimensione Formato  
HNN.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 491.24 kB
Formato Adobe PDF
491.24 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: http://hdl.handle.net/11311/546326
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 10
social impact