All posts by admin

History of ASL Annual Meetings

The Association for Symbolic Logic has hosted an Annual Meeting in North America in the spring of each year. With the cancellation of the 2020 meeting due to coronavirus concerns, this rich history is worth pausing to consider. Personally I attended relatively regularly during 2001–2019. (Meetings rotate between Midwest, East, West.)  
W 1999 UCSD
MW 2000 UIUC
E 2001 UPenn
W 2002 Las Vegas
MW 2003 UIC
E 2004 Carnegie Mellon
W 2005 Stanford
MW 2006 Montréal
E 2007 Gainesville, FL
W 2008 UC Irvine
MW 2009 Notre Dame
E 2010 Washington, DC
W 2011 Berkeley, CA
MW 2012 Madison, WI
E 2013 U Waterloo
W 2014 UC Boulder
MW 2015 UIUC
E 2016 UConn
W 2017 Boise State U.
MW 2018 Western Illinois U.
E 2019 CUNY Graduate Center
W 2020 *
*UC Irvine (cancelled).

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