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-01-01
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.