2025/10/09 by Chen, Joey, Kjos-Hanssen, Bjørn, Koswara, Ivan +2
#68Q06 (Secondary) #68Q30 #68Q45 (Primary) 03D05 #F.4.2 #F.4.3 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO)
paper · doi:10.48550/arxiv.2510.07696
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). For a finite alphabet Σ of at least two elements, we consider the non-deterministic automatic complexity given by exactly - yet not necessarily uniquely - accepting automata: a word x ∈ Σ^* has exact non-deterministic automatic complexity k ∈ ℕ if there exists a non-deterministic automaton of k states which accepts x while rejecting every other word of the same length as x, and no automaton of fewer states has this property. Importantly, and in contrast to the classical notion, the witnessing automaton may have multiple paths of computation accepting x. We denote this measure of complexity by ANe, and study a class of languages of low ANe-complexity defined as Lq = \ x ∈ Σ^* : ANe(x) < q|x| \, which is parameterised by rationals q ∈ (0,1/2) (generalising a class of sets first studied by Kjos-Hanssen). We show that for every q ∈ (0,1/2), this class is neither context-free nor recognisable by certain Boolean circuits. In the process, we answer an open question of Kjos-Hanssen quantifying the complexity of L1/3 in terms of Boolean circuits, and also prove the Shannon effect for ANe.