
Category Archives: research


VC-dimensions for nondeterministic finite automata

11th Int’l Conference on Computability, Complexity and Randomness 2016
https://www.youtube.com/watch?time_continue=2&v=1kTtBlYbk9s

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”.

Deontic Logic and proof assistants
Damir Dzhafarov, Stefan Kaufmann, Bjørn Kjos-Hanssen, Dave Ripley, et al., at the 2016 ASL Annual Meeting at UConn.
José Carmo and Andrew J.I. Jones have studied contrary-to-duties obligations in a series of papers.
They develop a logical framework for scenarios such as the following:
1. There ought to be no dog.
2. If there is a dog, there ought to be a fence.
One conjecture from Carmo and Jones 1997 was refuted in a rather technical way in my 1996 term paper at University of Oslo.
The conjecture stated that one could simply add the condition
$\DeclareMathOperator{\pii}{ob}$
$$
(Z \in \pii(X)) \land
(Y \subseteq X) \land
(Y \cap Z \ne \emptyset ) \rightarrow (Z \in \pii(Y )) \tag{5e}
$$
for the conditional obligation operator ob.
In a follow-up paper (2001) they argued that (5e) could be added by weakening some other conditions.
In a new paper in Studia Logica, and presented at the Association for Symbolic Logic Annual Meeting 2016 at UConn, I argue that (5d) and (5e) are in conflict with each other. The argument is a generalization and strengthening of the 1996 argument.
2018: Benzmüller et al. have implemented Carmo and Jones’ logic in the proof assistant Isabelle and Jake Fennick’s MA project is the implementation of my follow-up paper in Isabelle.

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.

The Turing Guide and computability in physics
A draft of my review for the Notices of the AMS (2019).