Non-context-free co-language conjecture for maximally complex words

Let L3L_3 be the language of maximally complex words for nondeterministic automatic complexity over the alphabet 0,1,2{0,1,2}, and let coCFL\operatorname{coCFL} denote the complements of context-free languages. Non-context-free co-language conjecture.

L3∉coCFL.L_3\not\in\operatorname{coCFL}.

This is proposed as an analogue of the fact that the set R={x:C(x)x}R=\{x:C(x)\geq\lvert x\rvert\} of random words belongs to coRE while L3L_3 is known to be CFL-immune but not coCFL-immune. The conjecture asserts that L3L_3 nevertheless does not belong to coCFL.

Sources & referencesView supporting material

Primary source

Bjørn Kjos-Hanssen, “On the complexity of automatic complexity”, arXiv:1607.06106 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.