{"id":"arxiv/2608.22271","url":"https://arxiv.org/abs/2608.22271","tags":["cs.FL","math.LO"],"score":0,"title":"Exact versus unique nondeterministic automatic complexity","domain":"cs.FL","source":"arxiv","authors":["Bjørn Kjos-Hanssen","Travis Rivera Petit"],"reviews":0,"subject":"cs.FL","summary":"The exact nondeterministic automatic complexity $A_{Ne}(x)$ of a word $x$ is the minimum number of states of a nondeterministic finite automaton that accepts $x$ and no other word of length $|x|$; the unique nondeterministic automatic complexity $A_N(x)$ additionally requires the accepting computation to be unique. Chen, Kjos-Hanssen, Koswara, Richter, and Stephan (FSTTCS 2025) asked whether the two measures can differ. We answer this affirmatively: the binary word $w=1101000000100$ satisfies $A_{Ne}(w)=6<7=A_N(w)$. The separation is witnessed by a six-state automaton whose sole accepted…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-23","reactions":{}}