Showing cs.CCShow all
3 papers · 1 filter
cs.CC2001
A New Approach to Formal Language Theory by Kolmogorov Complexity
Ming Li, Paul Vitanyi
We present a new approach to formal language theory using Kolmogorov complexity. The main results presented here are an alternative for pumping lemma(s), a new characterization for…
cs.CC1998
New Applications of the Incompressibility Method: Part I
Tao Jiang, Ming Li, Paul Vitanyi
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…
cs.CC1998
New Applications of the Incompressibility Method: Part II
Harry Buhrman, Tao Jiang, Ming Li +1
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…