We address the problem of finding examples of non-bireversible transducers defining free groups, we show examples of transducers with sink accessible from every state which generate free groups, and, in general, we link this problem to the non-existence of certain words with interesting combinatorial and geometrical properties that we call fragile words. By using this notion, we exhibit a series of transducers constructed from Cayley graphs of finite groups whose defined semigroups are free, and thus having exponential growth.

Fragile words and Cayley type transducers

D’angeli, Daniele;Rodaro, Emanuele
2018

Abstract

We address the problem of finding examples of non-bireversible transducers defining free groups, we show examples of transducers with sink accessible from every state which generate free groups, and, in general, we link this problem to the non-existence of certain words with interesting combinatorial and geometrical properties that we call fragile words. By using this notion, we exhibit a series of transducers constructed from Cayley graphs of finite groups whose defined semigroups are free, and thus having exponential growth.
File in questo prodotto:
File Dimensione Formato  
11311-1078155_Rodaro.pdf

accesso aperto

: Publisher’s version
Dimensione 243.91 kB
Formato Adobe PDF
243.91 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/1078155
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact