2 papers
cs.FL2026
Exact versus unique nondeterministic automatic complexity
Bjørn Kjos-Hanssen, Travis Rivera Petit
The exact nondeterministic automatic complexity of a word is the minimum number of states of a nondeterministic finite automaton that accepts and no other word…
cs.FL2025
Languages of Words of Low Automatic Complexity Are Hard to Compute
Joey Chen, Bjørn Kjos-Hanssen, Ivan Koswara +2
The automatic complexity of a finite word (string) is an analogue for finite automata of Sipser's distinguishing complexity (1983) and was introduced by Shallit and Wang (2001). Fo…