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

download_20190921_200022Angsheng Li announcing TAMC 2020.

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.

pic-CTFM

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.

Slides for Waterloo/Tokyo

Slides for Singapore 2019