Category Archives: research


A Conflict Between Some Semantic Conditions

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
(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, to appear 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.


The Complexity Option Game

2014 M.A. graduate Malihe Alikhani completed her Master’s project on American option pricing and optimal stopping for success runs. She participated in the Cornell Summer School in Probability 2014.

Her project constitutes one of the parts of the new paper Pricing Complexity Options, which appeared in
Algorithmic Finance, 2015.

Entry at IOS Press

The best version of the paper is at

The ideas are implemented in the Complexity Option Game!


Graduate Program in Logic

The Department of Mathematics at University of Hawaii at Manoa has long had an informal graduate program in logic, lattice theory, and universal algebra going back to Alfred Tarski’s student William Hanf.
Starting in 2016, things are getting a little more formal.

We intend the following course rotation (repeating after two years):

Semester Course number Course title
Fall 2015 MATH 649B Graduate Seminar
Spring 2016 MATH 649* Applied Model Theory
Fall 2016 MATH 654* Graduate Introduction to Logic
Spring 2017 MATH 657 Computability and Complexity

*Actual course numbers may vary.

Faculty who may teach in the program

David A. Ross, Professor
Bjørn Kjos-Hanssen, Professor
Mushfeq Khan, Temporary Assistant Professor 2014-2017
Achilles Beros, Temporary Assistant Professor 2015-2017

Documentation for the structure function calculator

$h^*_x(m)=q$ means that in order to have at most $\text{(alphabet size)}^{m}$ accepting paths of length $n=|x|$, we need $q$ states.


  • We are considering single-run complexity where the automaton must proceed to a fresh state except
    that there is one state that may be repeated.
  • Thus: the automaton need not be deterministic; a run may be abandoned midway;
  • the run can start before we get to the run-state;
  • runs that are of less than maximal length of their “flavor” (such as 322023 which is shorter than 20322023 in the given example) do count (they are in any case insignificant for statistical model selection purposes); runs of less than maximal length for their size-of-flavor (such as 2311322 for size 3) do count; in general any subrun of a run counts.

The provided example comes from a series of codons in part of a messenger RNA (mRNA) molecule whose genetic code is $$AUG\, ACG\, GAG\, CUU\, CGG\, AGC\, UAG$$
encoded as
which has length $n=21$ and is a string from the alphabet $\{0,1,2,3\}$ which has size $b=4$. There is a run of length $r=8$ from the subalphabet $j=\{0,2,3\}$, namely an occurrence of 20322023. The corresponding automaton has $q=n+1-r=21+1-8=14$ many states and accepts $|j|^r=3^8$ many strings of length $n$. When $3^8\le b^m$ we can then assert that $h^*(m)\le q$. Thus
6561 = 3^8\le 4^m
(4^2,4^3,4^4,4^5,4^6,4^7)= (16, 64, 256, 1024, 4096, 16384)
So $h^*(7)\le 14$.

The longest unary ($|j|=1$) run is of length $r=2$. This gives $q=n+1-r=20$ and only one string is accepted so $h^*(m)\le 20$ for all $m$.

The longest binary ($|j|=2$) run is of length $r=4$. This gives $q=n+1-r=18$ and when $2^4\le 4^m$ (i.e., $2\le m$), we can assert $h^*(m)\le q$. So $h^*(2)\le 18$.

What can we say about $h^*(6)$? $4^6=4096$ and
$(3^4,3^5,3^6,3^7,3^8)=(81, 243, 729, 2187, 6561)$. So
$$3^8\le 4^7\Longrightarrow h^*(7)\le 22-8=14$$
$$3^7=2187\le 4^6=4096\Longrightarrow h^*(6)\le 22-7=15$$
$$3^6= 729\le 4^5 = 1024\Longrightarrow h^*(5)\le 22-6=16$$
$$3^5= 243\le 4^4 = 256\Longrightarrow h^*(4)\le 22-5=17$$
$$3^4= 81 \le 4^4 = 256(\Longrightarrow h^*(4)\le 22-4=18)$$
$$3^3= 27\le 4^3 = 64\Longrightarrow h^*(3)\le 22-3=19$$
So we cannot obtain $h^*(3)\le 18$ by a partial ternary run, but we can obtain it because $h^*(2)\le 18$ because of the binary run.

$$3^r\le 4^1\Longrightarrow r\le 1$$
$$2^r\le 4^1\Longrightarrow r\le 2$$
So a binary run of length 2 narrows it down to $4^1$.
And this corresponds to
so $h^*(1)\le 20$.

Some examples of “inversion” (different explanation for the string depending on whether the subalphabet, or the size of the subalphabet, is taken into account):