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.

CHINA, NO PAPERS:

 1 2004 Beijing 2 2005 Kunming, China

CHINA, PAPERS:

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

INTERNATIONAL:

 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

Angsheng Li announcing TAMC 2020.

Humuhumunukunukuapua’a at the Symposium

2nd Annual SURE Symposium 2019

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

Extracting randomness within a subset

At the Association for Symbolic Logic Annual Meeting at CUNY Graduate Center in Manhattan, NY, I gave a talk in the Special Session on Computability Theory on joint work with Lu Liu.   Slides are available.

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.

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.