Automatic Complexity

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

John E. Hopcroft and Jeffrey D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley Series in Computer Science. Addison-Wesley Publishing Co., Reading, Mass., 1979.

6

Kayleigh Hyde. Nondeterministic finite state complexity. Master’s thesis, University of Hawaii at Manoa, U.S.A., 2013.

7

Kayleigh K. Hyde and Bjørn Kjos-Hanssen. Nondeterministic automatic complexity of overlap-free and almost square-free words. Electron. J. Combin., 22(3), 2015. Paper 3.22, 18.

8

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.

9

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.

10

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

11

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

12

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

13

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

14

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

15

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.

16

R. C. Lyndon and M. P. Schützenberger. The equation aM=bNcP in a free group. Michigan Math. J., 9:289–298, 1962.

17

Ernest Schimmerling. A course on set theory. Cambridge University Press, Cambridge, 2011.

18

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

19

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

20

M. Sipser. Introduction to the Theory of Computation. Cengage Learning, 2012.

21

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.