Sink components, rigid images, and a cubic upper bound for synchronizing automata without involutions

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 a reduction for arbitrary strongly connected synchronizing automata. If the graph of pairs of states has a sink component of a certain kind, then its pairs are collapsed within n−1 letters, and the Černý bound for the automaton follows from the bound for a smaller quotient. The proof is a short linear-algebra argument. For automata without involutions, this reduces the Černý bound to automata with no sink component of this kind, and we show that such automata exist, with 243 states. We then weaken what is needed for those automata, and we prove the Černý bound for automata without involutions whose letters have defect at most 1. By counting the smallest images with more than one state of the classes of a sink component, which we call rigid images, we prove the Černý bound for all automata without involutions with at most 12 states, and the bound n³/12 for all n ≥ 10. For a sink component whose rigid images have b ≥ 3 states, we map the states into a vector space over a finite field of characteristic dividing b so that words act as affine maps, every rigid image sums to zero, and the two states of each arc have different images. A lattice version of the dimension count reduces the Černý bound for the whole class to sink components whose rigid images span a lattice containing bℤ^Q. In a companion paper we prove the bound n−1 for circular automata and for automata preserving a tournament, and a quadratic lower bound for the class.

Authors

Institutions

Publication Details

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

Sink components, rigid images, and a cubic upper bound for synchronizing automata without involutions

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

Sink components, rigid images, and a cubic upper bound for synchronizing automata without involutions

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 a reduction for arbitrary strongly connected synchronizing automata. If the graph of pairs of states has a sink component of a certain kind, then its pairs are collapsed within n−1 letters, and the Černý bound for the automaton follows from the bound for a smaller quotient. The proof is a short linear-algebra argument. For automata without involutions, this reduces the Černý bound to automata with no sink component of this kind, and we show that such automata exist, with 243 states. We then weaken what is needed for those automata, and we prove the Černý bound for automata without involutions whose letters have defect at most 1. By counting the smallest images with more than one state of the classes of a sink component, which we call rigid images, we prove the Černý bound for all automata without involutions with at most 12 states, and the bound n³/12 for all n ≥ 10. For a sink component whose rigid images have b ≥ 3 states, we map the states into a vector space over a finite field of characteristic dividing b so that words act as affine maps, every rigid image sums to zero, and the two states of each arc have different images. A lattice version of the dimension count reduces the Černý bound for the whole class to sink components whose rigid images span a lattice containing bℤ^Q. In a companion paper we prove the bound n−1 for circular automata and for automata preserving a tournament, and a quadratic lower bound for the class.

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