# Publications

#### Submitted 2021

1. An incompressibility theorem for automatic complexity.
2. Bjørn Kjos-Hanssen, Saroj Niraula, Soowhan Yoon, Sabrina Hardisty, Guanhong Li, and Jacqueline Millard. A 1-parameter family of metrics connecting Jaccard distance to normalized information distance.

#### Submitted 2020

1. Bjørn Kjos-Hanssen, Clyde James Felix, Sun Young Kim, Ethan Lamb, and Davin Takahashi, VC-dimensions of nondeterministic finite automata for words of equal length. Electronic proceedings of International Symposium on Artificial Intelligence and Mathematics (ISAIM) 2020. Journal version submitted 04 Apr 2020, under review since 08 Oct 2020, under revision since 08 Feb 2021.

#### Submitted 2019

1. Bjørn Kjos-Hanssen and Lei Liu: The number of languages with maximum state complexity, Algebra Universalis (resubmitted 20 Jan 2021). Lecture Notes in Computer Science 11436 (2019), 394--409. TAMC 2019 (Theory and Applications of Models of Computation).

### Journal articles

1. Bjørn Kjos-Hanssen, Automatic complexity of Fibonacci and Tribonacci words. Discrete Applied Mathematics 289 (31 January 2021), 446--454.
2. Bjørn Kjos-Hanssen and Lu Liu: Extracting randomness within a subset is hard, European Journal of Mathematics 6 (2020), no. 4, 1438–1451.
3. Only human. Notices of the American Mathematical Society 66 (2019), no. 4, 556--561.
4. Few paths, fewer words: model selection with automatic structure functions. Experimental Mathematics 28 (2019), no. 1, 121--127.
5. Downey, Hirschfeldt and Kjos-Hanssen: Preface. Special issue on "Computability, complexity and randomness'' (CCR 2016). Held in Honolulu, January 4-8, 2016. Theory of Computing Systems 62 (2018) no. 7, 1553–1554.
6. Automatic complexity of shift register sequences. Discrete Mathematics 341 (2018), no. 9, 2409–2417. Lecture Notes in Computer Science 10388 (2017), 170-181. Workshop on Logic, Language, Information and Computation (WoLLIC) 2017.
7. Permutations of the integers induce only the trivial automorphism of the Turing degrees, Bulletin of Symbolic Logic 24 (2018), no. 2, 165-174. Downey Festschrift, Lecture Notes in Computer Science 10010 (2017) 599--607.
8. On the complexity of automatic complexity. Theory of Computing Systems 61 (2017), no. 4, 1427-–1439.
9. A conflict between some semantic conditions of Carmo and Jones for contrary-to-duty obligations, Studia Logica 105 (2017), no. 1, 173--178.
10. Covering the recursive sets (with Frank Stephan and Sebastiaan Terwijn), Annals of Pure and Applied Logic 168 (2017), no. 4, 804--823. Computability in Europe, Lecture Notes in Computer Science 9136 (2015), 44—53.
11. The Strength of the Grätzer-Schmidt theorem (with Katie Brodhead, Mushfeq Khan, William A. Lampe, Paul Kim Long V. Nguyen, and Richard A. Shore). Archive for Mathematical Logic 55 (2016), no. 5, 687—704. Computability in Europe, Lecture Notes in Computer Science 5635 (2009), 59—67.
12. Kolmogorov structure functions for automatic complexity. Theoretical Computer Science 607 (2015), no. 3, 435—445. Lecture Notes in Computer Science (COCOA 2014): Kolmogorov structure functions for automatic complexity in computational statistics.
13. Pricing complexity options (with M. Alikhani, A. Pakravan, and B. Saadat), Algorithmic Finance 4 (2015), no. 3-4, 127-137.
14. Nondeterministic automatic complexity of overlap-free and almost square-free words (with K. Hyde). Electronic Journal of Combinatorics 22 (2015), no. 3, Paper 3.22, 18 pp. Nondeterministic automatic complexity of almost square-free and strongly cube-free words, COCOON 2014, Lecture Notes in Computer Science 8591 (2014), 61—70.
15. Algorithmic randomness for Doob's martingale convergence theorem in continuous time (with Paul Kim Long V. Nguyen and Jason M. Rute). Logical Methods in Computer Science 10 (2014) no. 4, Paper 12.
16. How much randomness is needed for statistics? (with Antoine Taveneaux and Neil Thapen). Annals of Pure and Applied Logic 165 (2014), no. 9, 1470-1483. Computability in Europe, Lecture Notes in Computer Science 7318 (2012), 395—404.
17. Algorithmic aspects of Lipschitz functions (with Cameron Freer, André Nies, and Frank Stephan). Computability 3 (2014), no. 1, 45-61.
18. Randomness extraction and asymptotic Hamming distance (with Cameron Freer). Logical Methods in Computer Science 9 (2013) no. 3, Paper 27.
19. Arithmetic complexity via effective names for random sequences (with Frank Stephan and Jason R. Teutsch). ACM Transactions on Computational Logic 13, no. 3 (July 2012), Art. 24, 18 pp.
20. Lowness notions, measure, and domination (with Joseph S. Miller and Reed Solomon). Journal of the London Mathematical Society 85 (2012), no. 3, 869–888.
21. Martin-Löf randomness and Galton-Watson processes (with David Diamondstone). Annals of Pure and Applied Logic 163 (2012), no. 5, 519-529. Members of random closed sets. Computability in Europe, Lecture Notes in Computer Science 5635 (2009), 144—153.
22. A strong law of computationally weak subsets, Journal of Mathematical Logic 11 (2011) no. 1, 1—10. See also Electronic Colloquium on Computational Complexity, Report No. 150 (2010).
23. Kolmogorov complexity and the recursion theorem (with Wolfgang Merkle and Frank Stephan). Transactions of the American Mathematical Society 363 (2011) no. 10, 5465—5480. STACS 2006, Lecture Notes in Computer Science 3884 (2006), pp. 149—161.
24. Kolmogorov complexity and strong approximation of Brownian motion (with Tamás Szabados). Proceedings of the American Mathematical Society 139 (2011) no. 9, 3307—3316.
25. The probability distribution as a computational resource for randomness testing. Journal of Logic and Analysis 2 (2010), no. 10, 1—13.
26. Higher Kurtz randomness (with André Nies, Frank Stephan, and Liang Yu). Annals of Pure and Applied Logic 161 (2010), no. 10, 1280—1290.
27. Lattice initial segments of the hyperdegrees (with Richard A. Shore). Journal of Symbolic Logic 75 (2010), no. 1, 103—130.
28. Superhighness (with André Nies). Notre Dame Journal of Formal Logic 50 (2009), no. 4, 445—452.
29. Finding paths through narrow and wide trees (with Stephen E. Binns). Journal of Symbolic Logic 74 (2009), no. 1, 349—360.
30. Infinite subsets of random sets of integers. Mathematical Research Letters 16 (2009), no. 1, 103—110.
31. Effective dimension of points visited by Brownian motion (with Anil Nerode). Theoretical Computer Science 410 (2009), no. 4-5, 347—354. The law of the iterated logarithm for algorithmically random paths of Brownian motion. Logical Foundations of Computer Science, Lecture Notes in Computer Science 4514 (2007), pp. 310—317.
32. Self-embeddings of computable trees (with Stephen Binns, Manuel Lerman, Jim Schmerl, and Reed Solomon). Notre Dame Journal of Formal Logic 49 (2008), no. 1, 1—37.
33. Low for random reals and positive-measure domination. Proceedings of the American Mathematical Society 135 (2007), no. 11, 3703—3709 (electronic).
34. On a conjecture of Dobrinen and Simpson concerning almost everywhere domination (with Stephen Binns, Manuel Lerman, and Reed Solomon). Journal of Symbolic Logic 71 (2006), no. 1, 119—136.
35. Lowness for the class of Schnorr random reals (with André Nies and Frank Stephan). SIAM Journal on Computing 35 (2005), no. 3, 647—657 (electronic).
36. Comparing DNR and WWKL (with Klaus Ambos-Spies, Steffen Lempp, and Theodore A. Slaman). Journal of Symbolic Logic 69 (2004), no. 4, 1089—1104.
37. Local initial segments of the Turing degrees. Bulletin of Symbolic Logic 9 (2003), no. 1, 26—36.

#### Book and book chapters

1. Kjos-Hanssen and Birns: Statistics for Calculus Students. http://hdl.handle.net/10790/4572 Open Educational Resources (OER) textbook, Outreach College, University of Hawaii at Manoa, February 21, 2019.
2. The strength of some combinatorial principles related to Ramsey's theorem (with Denis R. Hirschfeldt, Carl G. Jockusch, Steffen Lempp, and Theodore A. Slaman.) Computational Prospects of Infinity. Part II: Presented Talks, Lecture Notes Series, Institute of Mathematical Sciences, National University of Singapore 15, World Scientific Publishing, Hackensack, NJ, 2008, pp. 143—162.
3. Immunity, diagonalisation and the complexity of mass problems (with Achilles Beros, Mushfeq Khan, and Andre Nies), Aspects of Computation. Lecture Notes Series, Institute of Mathematical Sciences, National University of Singapore 39, World Scientific Publishing, Hackensack, NJ (accepted). Combined final version of two conference papers:
4. A tractable case of the Turing automorphism problem: bi-uniformly $E_0$-invariant Cantor homeomorphisms. Higher recursion theory and set theory. Lecture Notes Series, Institute of Mathematical Sciences, National University of Singapore 40, World Scientific Publishing, Hackensack, NJ. Accepted.

#### Conference papers without a journal version yet

1. The strength of the Besicovitch-Davies theorem (with Jan Reimann), Computability in Europe, Lecture Notes in Computer Science 6158 (2010), 229—238.
2. Numberings and randomness (with Katie Brodhead). Computability in Europe, Lecture Notes in Computer Science 5635 (2009), 49—58.
3. Beros, Kjos-Hanssen, and Yogi: Planar digraphs for automatic complexity, Lecture Notes in Computer Science 11436 (2019), 59--73. TAMC 2019 (Theory and Applications of Models of Computation).
4. Kjos-Hanssen: A rigid cone in the truth-table degrees with jump, Downey Festschrift, Lecture Notes in Computer Science 10010 (2017), 487--500.
5. KL-randomness and effective dimension under strong reducibility (with David J. Webb). Computability in Europe, Lectures Notes in Computer Science, 2021.
6. On the degrees of constructively immune sets (with Samuel D. Birns). Computability in Europe, Lectures Notes in Computer Science, 2021.

### arXiv only

1. Lattice initial segments of the Turing degrees, doctoral dissertation, Logic and the Methodology of Science, University of California, Berkeley, 2002, iii+89 pages.
2. Effective Banach spaces, Master's thesis, Mathematics, University of Oslo, 1997.
3. Models of the Chisholm set, term paper for Filosofi hovedfag spesialområde 1, Fall 1996, University of Oslo. First cited in Carmo and Jones, Deontic logic and contrary-to-duties, Handbook of Philosophical Logic, 2002.
4. Google distance between words (with Alberto J. Evangelista). Presented at Frontiers in Undergraduate Research, University of Connecticut, 2006.

#### In quarantine

1. Counting pure states: a quantum variant of automatic complexity. Journal version. Conference version: Superposition as memory: unlocking quantum automatic complexity. Lecture Notes in Computer Science 10240 (2017), 160-169. Unconventional Computation and Natural Computation (UCNC) 2017.