MATH 657 Spring 2020

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.

History of TAMC

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.

TAMC venues:
First 6 conferences in China
The next 9 in China (3), Europe (2), Japan (2), Singapore, India
DBLP entry

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.


1 2004 Beijing
2 2005 Kunming, China


3 2006 Beijing
4 2007 Shanghai
5 2008 Xi’an
6 2009 Changsha


7 2010 Prague, Czech Republic
8 2011 Tokyo
9 2012 Beijing
10 2013 Hong Kong
11 2014 Chennai, India
12 2015 Singapore
13 2016 Xi’an
14 2017 Bern, Switzerland
15 2019 Kitakyushu, Japan
16 2020 Changsha

download_20190921_200022Angsheng Li announcing TAMC 2020.


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: The number of languages with maximum state complexity

Lei Liu completed her Master’s degree with the project title Complexity of Options in 2017.
An extension to monotone options (pictured) was presented at
ALH-2018. The new paper is called The number of languages with maximum state complexity and has been accepted for TAMC 2019.

Some of the 168 monotone Boolean functions of 4 variables


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