Simplicity and irreducibility in circular automata
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918410214965248 |
|---|---|
| author | Venturi, Riccardo |
| author_facet | Venturi, Riccardo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_16611 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simplicity and irreducibility in circular automata Venturi, Riccardo Formal Languages and Automata Theory Combinatorics Representation Theory 68Q70, 68Q45, 20M20, 20M30, 05E10 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. |
| title | Simplicity and irreducibility in circular automata |
| topic | Formal Languages and Automata Theory Combinatorics Representation Theory 68Q70, 68Q45, 20M20, 20M30, 05E10 |
| url | https://arxiv.org/abs/2511.16611 |