Linear reset thresholds for synchronizing automata without involutions: tournaments and circular automata
An automaton is without involutions if no input word swaps two states. For synchronizing automata of this kind, no strongly connected example with reset threshold at least the number n of states has been known, and only a linear lower bound has been recorded. We prove linear upper bounds for two natural subclasses, and we show that strong connectivity is essential. If every letter of a synchronizing automaton preserves a tournament on its states, then its reset threshold is at most n − 1; it is at most n − 2 if the tournament contains a directed 3-cycle, and at most n − 3 if moreover the automaton is strongly connected and n ≥ 4. All three bounds are sharp. This extends the bound n − 1 for monotonic automata from linear orders to arbitrary tournaments. Call an automaton circular if some word acts as a cyclic permutation of all states. If a circular automaton without involutions has a prime number of states, then every word acts as a permutation or a constant map, so a synchronizing one is reset by a single letter. For every odd n we determine the exact maximum reset threshold of synchronizing circular automata without involutions. It is 1 + p₁ + p₁p₂ + … + p₁⋯p_{s−1}, where p₁ ≥ … ≥ p_s are the prime factors of n, and it is at most (n − 1)/2. Without strong connectivity the reset threshold can be quadratic: binary automata without involutions reach (n² + 2n − 7)/4 for every n. We conjecture that strongly connected synchronizing automata without involutions have reset threshold at most n − 1, a bound attained for every n.
Authors
- Adam Wolf (ORCID: https://orcid.org/0009-0005-3007-649X)
Institutions
- Charles University (CZ)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-13
- DOI
- https://doi.org/10.5281/zenodo.24207619
- Primary Topic
- semigroups and automata theory
- Type
- preprint