Preprint
Aug 2026
Exact versus unique nondeterministic automatic complexity
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. Che...
B. Kjos-Hanssen, T. Petit
· 0 citations