Automatic Complexity

Download: Report, Slides


We studied notions of Kolmogorov complexity of binary strings in automata theory and context free grammars. We proved upper and lower bounds for general strings and studied 5 specific classes of binary strings. In particular, one of the new results proved was that the infinite Morse-Thue sequence has a constant complexity in our complexity definition.

Davin Choo
Student of life

I enjoy learning about things.