Path automata: compression thresholds, a floor(4n/3) construction for every n, and exact reset thresholds

We study a family of deterministic automata with two input letters. For every n >= 9 it contains a strongly connected synchronizing automaton with a state for which the minimum length of a word merging it with some other state is floor(4n/3). We determine this quantity in several parameter ranges. We also prove rt(B_(s,s)) = 3s^2+4s-1 for s >= 3; rt(B_(s,s+1)) = 3(s+1)^2 for odd s >= 3; and rt(B_(s,s+2)) = 3s^2+8s+8 for s >= 6 divisible by 3, with rt(B_(3,5)) = 58 separately. The lower bounds use families covering all successive inverse images, with integer labels controlling word length. The technical supplement contains the complete rules and their checks over the stated unbounded ranges. The complete two-parameter reset formula remains open. Preprint. Not externally peer reviewed. The main paper is accompanied by a required technical supplement and computational evidence archives.

Authors

Institutions

Publication Details

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

Path automata: compression thresholds, a floor(4n/3) construction for every n, and exact reset thresholds

Enkai Zhang
Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
preprint

Path automata: compression thresholds, a floor(4n/3) construction for every n, and exact reset thresholds

Enkai Zhang
preprint en

Abstract

We study a family of deterministic automata with two input letters. For every n >= 9 it contains a strongly connected synchronizing automaton with a state for which the minimum length of a word merging it with some other state is floor(4n/3). We determine this quantity in several parameter ranges. We also prove rt(B_(s,s)) = 3s^2+4s-1 for s >= 3; rt(B_(s,s+1)) = 3(s+1)^2 for odd s >= 3; and rt(B_(s,s+2)) = 3s^2+8s+8 for s >= 6 divisible by 3, with rt(B_(3,5)) = 58 separately. The lower bounds use families covering all successive inverse images, with integer labels controlling word length. The technical supplement contains the complete rules and their checks over the stated unbounded ranges. The complete two-parameter reset formula remains open. Preprint. Not externally peer reviewed. The main paper is accompanied by a required technical supplement and computational evidence archives.

Zenodo (CERN European Organization for Nuclear Research)
University of Toronto (CA)
Sustainable cities and communities
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.