In this paper we combine the algebraic properties of Mealy machines generating selfsimilar groups and the combinatorial properties of the corresponding deterministic finite automata (DFA). In particular, we relate bounded automata to finitely generated synchronizing automata and characterize finite automata groups in terms of nilpotency of the corresponding DFA. Moreover, we present a decidable sufficient condition to have free semigroups in an automaton group. A series of examples and applications is widely discussed, in particular we show a way to color the de Bruijn automata into Mealy automata whose associated semigroups are free, and we present some structural results related to the associated groups.

Groups and semigroups defined by colorings of synchronizing automata

D'Angeli D.;Rodaro E.
2014

Abstract

In this paper we combine the algebraic properties of Mealy machines generating selfsimilar groups and the combinatorial properties of the corresponding deterministic finite automata (DFA). In particular, we relate bounded automata to finitely generated synchronizing automata and characterize finite automata groups in terms of nilpotency of the corresponding DFA. Moreover, we present a decidable sufficient condition to have free semigroups in an automaton group. A series of examples and applications is widely discussed, in particular we show a way to color the de Bruijn automata into Mealy automata whose associated semigroups are free, and we present some structural results related to the associated groups.
File in questo prodotto:
File Dimensione Formato  
Groups and Semigroups defined by colorings.pdf

Accesso riservato

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