Kolmogorov Complexity and Deterministic Context-Free Languages
Oliver Glier · SIAM Journal on Computing · 2003
We deal with a criterion for deterministic context-free languages that was originally formulated by Li and Vitányi [SIAM J. Comput., 24 (1995), pp. 398-410]. Their result---called the KC-DCF lemma---relates Kolmogorov complexity to pushdown automata and works on a superset of examples compared to traditional iteration and pumping lemmas. Sadly, their KC-DCF lemma has a flaw. In this paper, we give a counterexample to the original KC-DCF lemma and also provide a corrected version.