5 problems

Linear-space recognition conjecture. Recognising $L_q$ in linear space is equivalent to recognising it via a linearly bounded automaton.

Let $\mathbf{f}^{(2)}$ denote the Fibonacci word, and let $\overline{\mathrm{A_N}}(\mathbf{f}^{(2)})$ be its limiting nondeterministic automatic complexity rate. Let…

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…