Category Archives: research
Computability and Automatic Complexity
This new 42,000 USD grant from the Simons Foundation will support travel and collaboration during 2020-2025.
Pictured: Angsheng Li announcing TAMC 2020 in Changsha, China during TAMC 2019 in Kitakyushu, Japan.
Automatic complexity of Fibonacci arrays
VC-dimensions for nondeterministic finite automata
11th Int’l Conference on Computability, Complexity and Randomness 2016
Humuhumunukunukuapua’a at the Symposium
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”.
TAMC 2019: Planar digraphs for automatic complexity
Kaui Yogi completed his Master project in Spring 2018. With Achilles Beros we have a new paper on Planar digraphs for automatic complexity based in part on Yogi’s project work and accepted at TAMC 2019.
Permutations of the integers and Aut($\mathcal D_T$)
Two papers on restrictions on automorphisms of Turing and truth-table degrees appeared in the Downey Festschrift for the Computability and Complexity Symposium 2017 in honour of Rod Downey’s 60th birthday.
One, “Permutations of the integers induce only the trivial automorphism of the Turing degrees”, appeared in Bulletin of Symbolic Logic (2018), and was presented at Workshop on Computability Theory in Waterloo, Ontario, and Workshop on Computability Theory and Foundations of Mathematics (CTFM) in Tokyo.