Non-context-free co-language conjecture for maximally complex words
Non-context-free co-language conjecture for maximally complex words
Let be the language of maximally complex words for nondeterministic automatic complexity over the alphabet , and let denote the complements of context-free languages. Non-context-free co-language conjecture.
This is proposed as an analogue of the fact that the set of random words belongs to coRE while is known to be CFL-immune but not coCFL-immune. The conjecture asserts that 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.