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.
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”.
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.
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.
The Simons Foundation under the program Collaboration Grants for Mathematicians (#315188 to Bjørn Kjos-Hanssen, grant title “Automatic Complexity”) supported my travel during 2014–2019.
Year
Trips
2014 – 2015
COCOA 2014 (Maui); U. Washington; Varieties of Algorithmic Information; CCR, Heidelberg; Haidar to Arizona Winter School
2015 – 2016
ASL Annual Meeting, UConn (myself and Beros); SIAM Meeting on Discrete Math, Atlanta
2016 – 2017
WoLLIC, London; UCNC, Arkansas
2017 – 2018
Workshop on Computability Theory, Waterloo
2018 – 2019
Computability Theory and Foundations of Mathematics, Tokyo; Joint Math Meetings, Baltimore
Nine subprojects
Here are papers produced about automatic complexity, many with Master’s students.
Conferences in parentheses are those with no published proceedings.
Students or consultants in parentheses discussed the topic but were not coauthors.
Title:
Kolmogorov structure functions for automatic complexity
Abstract:
We study an analogue of Kolmogorov’s notion of structure function, introduced in 1973, with Kolmogorov complexity replaced by Shallit and Wang’s (2001) automatic complexity. We discuss the prospects for using it for model selection in statistics. We prove an upper bound which is piecewise smooth, related to the binary entropy function, and appears to be fairly sharp based on numerical evidence.
LFSRs (linear feedback shift registers) are popular pseudorandomness generators.
In a new project we show that they generate output (often called $m$-sequences) of maximal (nondeterministic path-based) automatic complexity. At this point we have an experimental result, one which would have probability $2^{-93}$ to occur “by chance”, as well as a theoretical but sub-optimal result.
Moreover, an $m$-sequence of length 31 provides an example of a word $x$ such that
$$
A^-(x)=A_N(x)+2
$$
where $A_N$ is nondeterministic path-based automatic complexity, and $A^-$ is non-total deterministic automatic complexity.
Such an example (where $A^-(x)-A_N(x)>1$) was not known before the consideration of LFSRs in this area. That consideration was an idea of Jason Castiglione.
The paper has been accepted at WoLLIC 2017 and in journal form for Discrete Mathematics (2018).
This project was presented at the poster session of the SIAM Conference on Discrete Mathematics 2016 in Atlanta, Georgia. The session was otherwise dominated by interesting work on RNA pseudoknots and chord diagrams (3 out of 6 posters) which in the case of the work of the Biocomplexity Institute researchers Ricky Chen and Thomas Li involves modeling with multiply context-free grammars.