{
  "abstract": "Let $\\mathcal A$ 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 $\\mathrm{minext}(S)$ be the length of a shortest word $u$ with $|Su^{-1}|>|S|$, where $Su^{-1}=\\{q: q\\cdot u\\in S\\}$. To each state $q$ attach the integer $β^{\\ast}_q=\\sum_{t=1}^{n-1}k^{\\,n-1-t}(\\mathrm{indeg}_t(q)-k^{t})$, where $\\mathrm{indeg}_t(q)$ counts the pairs $(p,u)$ with $|u|=t$ and $p\\cdot u=q$, and let $B(S)=\\sum_{q\\in S}β^{\\ast}_q$. On every synchronizing automaton, $B(S)\\ge0$ implies $\\mathrm{minext}(S)\\le n-1$, so, as $B(Q)=0$, one of $S$ and $Q\\setminus S$ extends within $n-1$; when $B(S)>0$ no hypothesis is needed. Kari's Eulerian extension lemma is the case $β^{\\ast}=0$, and $β^{\\ast}$, like every member of the family $\\sum_{t=1}^{n-1}c_tσ_t$, $c_t>0$, vanishes identically if and only if the automaton is Eulerian, where $σ_t(S)=\\sum_{q\\in S}(\\mathrm{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)\\ge0$ 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\\le7$. Along non-Eulerian automata whose words of length $n-1$ merge a fraction of the state pairs bounded below, with $\\max_q\\mathrm{indeg}_{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\\ge4$) 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$.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.21603",
  "author_total": 1,
  "authors": [
    {
      "name": "Michele Miccinesi"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/a20jjdmb7ja31.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.21603",
  "fulltext_url": null,
  "id": "a20jjdmb7ja31",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.21603",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DM"
    ],
    [
      "arxiv",
      "cs.FL"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|semigroups and automata theory"
    ]
  ],
  "openalex": "W7213903658",
  "pdf_url": "https://arxiv.org/pdf/2609.21603",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-18",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/a20jjdmb7ja31.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:23:07Z",
      "native_id": "2609.21603",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.21603"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Certificates for short extending words in a finite automaton",
  "title_text": "Certificates for short extending words in a finite automaton",
  "type": "preprint",
  "updated_at": "2026-10-30T12:23:07Z",
  "url": "https://research.draconitic.com/paper/a20jjdmb7ja31",
  "venue": "arXiv",
  "versions": []
}