Certificates for short extending words in a finite automaton
Abstract
Let 𝒜 be a complete deterministic finite automaton on a state set Q of size n with k letters, and for a proper nonempty subset S of Q let minext(S) be the length of a shortest word u with |Su−1|>|S|, where Su−1={q: q· u∈ S}. To each state q attach the integer β∗q=∑t=1n−1k n−1−t(indegt(q)−kt), where indegt(q) counts the pairs (p,u) with |u|=t and p· u=q, and let B(S)=∑q∈ Sβ∗q. On every synchronizing automaton, B(S)≥0 implies minext(S)≤ n−1, so, as B(Q)=0, one of S and Q∖ S extends within n−1; when B(S)>0 no hypothesis is needed. Kari's Eulerian extension lemma is the case β∗=0, and β∗, like every member of the family ∑t=1n−1ctσt, ct>0, vanishes identically if and only if the automaton is Eulerian, where σt(S)=∑q∈ S(indegt(q)−kt). On strongly connected automata σt(S)/kt has Cesàro limit n e(S)/e(Q)−|S| for Friedman's weight e; that limit certifies singletons but no larger subset in general. The hypothesis B(S)≥0 cannot be relaxed by one integer unit, nor can the constant n−1 be improved. A second-moment test on the sizes |Su−1| certifies 60 to 95 percent of the subsets with B(S)<0 at n≤7. Along non-Eulerian automata whose words of length n−1 merge a fraction of the state pairs bounded below, with maxqindegn−1(q)=o(nkn−1), it certifies all but a vanishing share of them. The functional B certifies half of the subsets outside {B=0}. At each subset size coprime to n (n≥4) some synchronizing Eulerian binary automaton attains the constant n−1; whether only there is open. No reset bound follows: Černý's automata have subsets not extending within n−1.
Related
- Smallest String Attractors and Minimal Coverage Certificates of Thue--Morse Words
- Surface subgroups of Baumslag doubles along short words
- A Finite Automaton Approach to Combinatorial Games
- Finite identity bases for flat semirings of linear words
- Closed-Relational Reconstruction Systems: Viability, Observable-History Lifting, and Finite Obstruction Certificates
BibTeX
@misc{miccinesi2026certificates,
title = {{Certificates for short extending words in a finite automaton}},
author = {Michele Miccinesi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21603},
eprint = {2609.21603},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21603},
}
RIS
TY - UNPB
TI - Certificates for short extending words in a finite automaton
AU - Michele Miccinesi
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21603
UR - https://arxiv.org/abs/2609.21603
AB - Let 𝒜 be a complete deterministic finite automaton on a state set Q of size n with k letters, and for a proper nonempty subset S of Q let minext(S) be the length of a shortest word u with |Su^−1|>|S|, where Su^−1={q: q· u∈ S}. To each state q attach the integer β^∗_q=∑_t=1^n−1k^ n−1−t(indeg_t(q)−k^t), where indeg_t(q) counts the pairs (p,u) with |u|=t and p· u=q, and let B(S)=∑_q∈ Sβ^∗_q. On every synchronizing automaton, B(S)≥0 implies minext(S)≤ n−1, so, as B(Q)=0, one of S and Q∖ S extends within n−1; when B(S)>0 no hypothesis is needed. Kari's Eulerian extension lemma is the case β^∗=0, and β^∗, like every member of the family ∑_t=1^n−1c_tσ_t, c_t>0, vanishes identically if and only if the automaton is Eulerian, where σ_t(S)=∑_q∈ S(indeg_t(q)−k^t). On strongly connected automata σ_t(S)/k^t has Cesàro limit n e(S)/e(Q)−|S| for Friedman's weight e; that limit certifies singletons but no larger subset in general. The hypothesis B(S)≥0 cannot be relaxed by one integer unit, nor can the constant n−1 be improved. A second-moment test on the sizes |Su^−1| certifies 60 to 95 percent of the subsets with B(S)<0 at n≤7. Along non-Eulerian automata whose words of length n−1 merge a fraction of the state pairs bounded below, with max_qindeg_n−1(q)=o(nk^n−1), it certifies all but a vanishing share of them. The functional B certifies half of the subsets outside {B=0}. At each subset size coprime to n (n≥4) some synchronizing Eulerian binary automaton attains the constant n−1; whether only there is open. No reset bound follows: Černý's automata have subsets not extending within n−1.
ER -