Automatic Complexity

Over summer of 2019, I worked with Professor Kjos-Hanssen and a group of other students on automatic complexity research. Our aim was to find the lower bound of a string by finding patterns within it and tracking the number of repetitions. To model this, we used finite automata and programming to determine the number of states for each string can have, as well as to determine the number of repetitions within it.

One application of this is regular expressions/regex, which is used in language techology as text replacement/searches, amongst other things. It also applies to the widely known Fibonacci words, as well as the lesser known Tribonacci words, and can also demonstrate reduplication.

This project was done in a group, and it involved discussions to ensure that we understood the principles and theories, as well as how we were going to utilize and apply them to the research question throughout the research process. At the end of the summer, the other students and I presented our work at the Summer Undergraduate Research Symposium. The link to the slides is below.

Here is the presentation from the Symposium.