|W||2017||Boise State U.|
|MW||2018||Western Illinois U.|
|E||2019||CUNY Graduate Center|
Course title: “Recursive functions and complexity”
Textbook title: “A second course in formal languages and automata theory” by J. Shallit
Despite the intimidating titles this is just a graduate introduction to automata, computability, and complexity.
Possible additional topics: Automatic complexity and Python programming.
The conference series Theory and Applications of Models of Computation deserves a history post.
My impression is that it started as a Chinese counterpart to Computability in Europe and S. Barry Cooper was involved with starting up both.
First 6 conferences in China
The next 9 in China (3), Europe (2), Japan (2), Singapore, India
B. Kjos-Hanssen gave two special session talks in 2007, and had 2 accepted papers in 2019.
The conference was held every year since 2004 except for 2018.
There seem to have been roughly speaking three periods.
CHINA, NO PAPERS:
|7||2010||Prague, Czech Republic|
SURE: Summer Undergraduate Research Experience
will feature two projects mentored by Prof. Kjos-Hanssen:
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.
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”.