Automatic Complexity

Download: Report , Slides

Overview

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.