Synchronizing automata without involutions: circular automata, tournaments, and a quadratic lower bound

An automaton is without involutions if no input word swaps two states. These automata form one of the classes in Volkov's list of results on the Černý conjecture (entry A8), which records that no strongly connected example with reset threshold at least its number of states is known. We prove that if an automaton without involutions has an odd prime number p of states and some word acts as a cyclic permutation of all states, then every word acts as a permutation or as a constant map. Consequently, if such an automaton is synchronizing, it is reset by a single letter. So no strongly connected example of the kind above exists among circular automata of prime order. An explicit example with 9 states shows that primality cannot be dropped. For general (not necessarily strongly connected) automata without involutions, we give binary automata with reset threshold exactly m(L+2)−1 on m+L+1 states, for every odd m. This yields reset thresholds of at least (n²+2n−7)/4 for every n ≥ 2, whereas the list records only the linear lower bound n+⌊n/2⌋−2. We also observe that Pribavkina's binary slowly synchronizing automata with zero are without involutions when their parameter k = n/2 is odd. They have reset threshold n²/4+n/2−1, the value our family gives for every even n. Next, we prove that a strongly connected synchronizing automaton whose letters preserve a tournament has reset threshold at most n−1, which extends the classical bound for strongly connected monotonic automata. The proof uses the modules of the tournament. For synchronizing circular automata without involutions of composite order n, we prove rt ≤ (n−1)/2. With the prime case, all synchronizing circular automata without involutions have rt < n. We determine the exact maximum of rt for these automata for every odd n ≥ 3. Finally, we conjecture that strongly connected automata without involutions have reset threshold at most n−1, and we show that this bound, if true, is attained for every n.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-12
DOI
https://doi.org/10.5281/zenodo.24176978
Primary Topic
semigroups and automata theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Synchronizing automata without involutions: circular automata, tournaments, and a quadratic lower bound

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

Synchronizing automata without involutions: circular automata, tournaments, and a quadratic lower bound

Adam Wolf
preprint en

Abstract

An automaton is without involutions if no input word swaps two states. These automata form one of the classes in Volkov's list of results on the Černý conjecture (entry A8), which records that no strongly connected example with reset threshold at least its number of states is known. We prove that if an automaton without involutions has an odd prime number p of states and some word acts as a cyclic permutation of all states, then every word acts as a permutation or as a constant map. Consequently, if such an automaton is synchronizing, it is reset by a single letter. So no strongly connected example of the kind above exists among circular automata of prime order. An explicit example with 9 states shows that primality cannot be dropped. For general (not necessarily strongly connected) automata without involutions, we give binary automata with reset threshold exactly m(L+2)−1 on m+L+1 states, for every odd m. This yields reset thresholds of at least (n²+2n−7)/4 for every n ≥ 2, whereas the list records only the linear lower bound n+⌊n/2⌋−2. We also observe that Pribavkina's binary slowly synchronizing automata with zero are without involutions when their parameter k = n/2 is odd. They have reset threshold n²/4+n/2−1, the value our family gives for every even n. Next, we prove that a strongly connected synchronizing automaton whose letters preserve a tournament has reset threshold at most n−1, which extends the classical bound for strongly connected monotonic automata. The proof uses the modules of the tournament. For synchronizing circular automata without involutions of composite order n, we prove rt ≤ (n−1)/2. With the prime case, all synchronizing circular automata without involutions have rt < n. We determine the exact maximum of rt for these automata for every odd n ≥ 3. Finally, we conjecture that strongly connected automata without involutions have reset threshold at most n−1, and we show that this bound, if true, is 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