Category Archives: research

2019-08-02

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

tall-asl

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.

Slides

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.