3 problems

Let $L_3$ be the language of maximally complex words for nondeterministic automatic complexity over the alphabet ${0,1,2}$, and let $\operatorname{coCFL}$ denote the complements of…

Let $A_N$ denote nondeterministic automatic complexity. For a random infinite binary sequence, let $D_n$ be the nondeterministic automatic complexity deficiency of its length-$n$ p…

Let $h_x(m)$ be the minimum number of states of a nondeterministic finite automaton accepting $x$ and at most $b^m$ strings of length $\lvert x\rvert$, let…