2nd Annual SURE Symposium 2019

SURE: Summer Undergraduate Research Experience

will feature two projects mentored by Prof. Kjos-Hanssen:

VC-dimensions of nondeterministic finite automata for words of equal length

Davin Takahashi and Ethan Lamb

Ishigami and Tani studied VC-dimensions of finite automata. We show that their results apply to a new notion, lower VC-dimension, where all sets (instead of some set) of a given cardinality must be shattered. We also relate the VC-dimension to the Separating Words problem.

Savings from word powers in automatic complexity

Sun Young Kim and Clyde Felix

The automatic complexity of a word was introduced by Shallit and Wang in 2001 and studied further by Kjos-Hanssen since 2013. In this work we develop an implementation of a lower bound on the complexity involving occurrences of powers of words, such as the occurrence of “humu” twice in “humuhumunukunukuapua’a”.