Bibliography

1

G. J. Chaitin. Algorithmic information theory. IBM Journal of Research and Development, 21(4):350–359, 1977.

2

Thierry Coquand and Gérard Huet. The calculus of constructions. Inform. and Comput., 76(2-3):95–120, 1988.

3

Pierluigi Crescenzi, Deborah Goldman, Christos Papadimitriou, Antonio Piccolboni, and Mihalis Yannakakis. On the complexity of protein folding. Journal of Computational Biology : a journal of computational molecular cell biology, 5:423–65, 02 1998.

4

Leonardo Mendonça de Moura, Soonho Kong, Jeremy Avigad, Floris van Doorn, and Jakob von Raumer. The Lean Theorem Prover (System Description). In Amy P. Felty and Aart Middeldorp, editors, CADE, volume 9195 of Lecture Notes in Computer Science, pages 378–388. Springer, 2015.

5

Liam Jordon and Philippe Moser. On the difference between finite-state and pushdown depth. In SOFSEM 2020: theory and practice of computer science, volume 12011 of Lecture Notes in Comput. Sci., pages 187–198. Springer, Cham, [2020] ©2020.

6

Liam Jordon and Philippe Moser. Normal sequences with non-maximal automatic complexity. In Mikolaj Bojanczyk and Chandra Chekuri, editors, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021, December 15-17, 2021, Virtual Conference, volume 213 of LIPIcs, pages 47:1–47:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

7

Bjørn Kjos-Hanssen. Complexity lookup. http://math.hawaii.edu/wordpress/bjoern/complexity-of-0110100110010110/.

8

Bjørn Kjos-Hanssen. Complexity option game. http://math.hawaii.edu/wordpress/bjoern/complexity-option-game/.

9

Bjørn Kjos-Hanssen. On the complexity of automatic complexity. Theory Comput. Syst., 61(4):1427–1439, 2017.

10

Dexter Kozen and Alexandra Silva. Practical coinduction. Math. Structures Comput. Sci., 27(7):1132–1152, 2017.

11

Dalia Krieger. On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci., 376(1-2):70–88, 2007.

12

Ming Li and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Graduate Texts in Computer Science. Springer-Verlag, New York, second edition, 1997.

13

R. C. Lyndon and M. P. Schützenberger. The equation \(a^{M}=b^{N}c^{P}\) in a free group. Michigan Math. J., 9:289–298, 1962.

14

Jeffrey Shallit. A Second Course in Formal Languages and Automata Theory. Cambridge University Press, New York, NY, USA, 1 edition, 2008.

15

Jeffrey Shallit and Ming-Wei Wang. Automatic complexity of strings. J. Autom. Lang. Comb., 6(4):537–554, 2001. 2nd Workshop on Descriptional Complexity of Automata, Grammars and Related Structures (London, ON, 2000).

16

Michael Sipser. A complexity theoretic approach to randomness. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, pages 330–335, New York, NY, USA, 1983. ACM.