Exact versus unique nondeterministic automatic complexity: the missing length-16 automaton, explicit witnesses at lengths 15 and 16, and complete censuses at lengths 14 and 15

Abstract

For a word x over a finite alphabet, A_(Ne)(x) is the least number of states of a nondeterministic finite automaton that accepts x and no other word of length |x|, and A_(N)(x) is the least number of states of one that in addition accepts x along a single computation; always A_(Ne)(x) ≤ A_(N)(x). Kjos-Hanssen and Rivera Petit have recently shown that the inequality can be strict, that 13 is the least length at which it can be, and that up to renaming of letters the separating words of length 13 are exactly the 365 letter-mergings of 0123444445126. They also print a table of the pairs (A_(Ne), A_(N)) at lengths 13 through 17, but leave the rows for lengths 15 and 16 without a witness of any kind: their length-15 automaton diagram carries no letters on any arrow, and there is no length-16 diagram at all. (At lengths 13, 14 and 17 a word is printed, or recoverable from a labelled diagram.) We supply the missing witnesses and certify them. The word 0123444444445126 = 0123 4⁸ 5126 — their length-13 witness with its run of fours lengthened from five to eight — satisfies A_(Ne) = 8 < 9 = A_(N), with an explicit eight-state exactly accepting automaton and an explicit nine-state uniquely accepting one; deleting its last letter leaves a length-15 word with A_(Ne) = 7 < 8 = A_(N). Two further separating words of length 16 and the reversal of the length-15 one are certified in the same way. We also carry the census two lengths further: at length 14 exactly 20 words separate the two measures, all letter-mergings of 01233333333401, all with (A_(Ne), A_(N)) = (6,7), and each of the twenty is certified individually; at length 15 exactly 74 do, forming 37 reversal pairs, all with (A_(Ne), A_(N)) = (7,8), and none of them binary, although lengths 13 and 14 both carry binary witnesses. The Hyde–Kjos-Hanssen bound A_(N)(x) ≤ ⌊ n/2 ⌋ + 1 is verified for all 190,899,322 canonical words of length 14, one length beyond the published verification. Every value stated below is machine-checked in Lean 4 except where it is explicitly labelled otherwise: the two censuses, the bound verification and a handful of auxiliary counts are computations outside the formal development.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   51e67c507e1f5794b821e5db86b62852a6a7fa18c3aeaa0c3974fad8923fe190