Simplicity and irreducibility in circular automata
This work addresses theoretical problems in automata theory for researchers, offering incremental advancements by refining definitions and extending known results to new contexts.
The paper tackles the problem of characterizing when circular synchronizing deterministic finite automata (DFAs) are simple (primitive) and irreducible under a modified definition over complex numbers, establishing that simplicity is fully characterized by the weak contracting property and providing conditions for irreducibility in contracting automata.
This paper investigates the conditions under which a given circular (synchronizing) DFA is \emph{simple} (sometimes referred to as \emph{primitive}) and when it is \emph{irreducible}. Our notion of irreducibility slightly differs from the classical one, since we are considering our monoid representations to be over $\mathbb{C}$ instead of $\mathbb{Q}$; nevertheless, several well-known results remain valid-for instance, the fact that every irreducible automaton is necessarily simple. We provide a complete characterization of simplicity in the circular case by means of the \emph{weak contracting property}. Furthermore, we establish necessary and sufficient conditions for a circular \emph{contracting automaton} (a stronger condition than the weakly contracting one) to be irreducible, and we present examples illustrating our results.