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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Linear reset thresholds for synchronizing automata without involutions: tournaments and circular automata

Adam Wolf
1 links
Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
preprint

Linear reset thresholds for synchronizing automata without involutions: tournaments and circular automata

Adam Wolf
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Charles University (CZ)
semigroups and automata theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon