B. Kjos-Hanssen

activity

20092026

most citedKolmogorov complexity and the Recursion Theorem

76 citations · 440 across the 53 of their papers we have counts for

collaborators

61 papers

quant-ph2026

Quantum Černý complexity of binary words

Pui Hang Lee, Pui-Yee Lee, Bjørn Kjos-Hanssen

We introduce the quantum Černý complexity $qc (w)$ of a binary word $w$ : the least dimension $d$ for which there exist quantum channels $A_{0}, A_{1}$ on $d \times d$ density mat…

cs.DM2026

The exact asymptotic constant in the metric dimension of Jaccard space

Bjørn Kjos-Hanssen

Let $X$ be a finite set with $∣ X ∣ = n$ and let $Jac (a, b) = ∣ a △ b ∣/∣ a \cup b ∣$ be the Jaccard distance on the power set $2^{X}$ . Lladser and Paradise recently proved t…

cs.FL2026

Exact versus unique nondeterministic automatic complexity

Bjørn Kjos-Hanssen, Travis Rivera Petit

The exact nondeterministic automatic complexity $A_{N e} (x)$ of a word $x$ is the minimum number of states of a nondeterministic finite automaton that accepts $x$ and no other word…

cs.FL2026

Every string has probabilistic automatic complexity at most three

Bjørn Kjos-Hanssen

Gill (arXiv:2402.13376) introduced the probabilistic automatic complexity $A_{P} (w)$ of a finite string $w$ : the least number of states of a probabilistic finite automaton (PFA) for…

cs.FL2025

Languages of Words of Low Automatic Complexity Are Hard to Compute

Joey Chen, Bjørn Kjos-Hanssen, Ivan Koswara +2

The automatic complexity of a finite word (string) is an analogue for finite automata of Sipser's distinguishing complexity (1983) and was introduced by Shallit and Wang (2001). Fo…

cs.FL2023

Conditional automatic complexity and its metrics

Bjørn Kjos-Hanssen

Li, Chen, Li, Ma, and Vitányi (2004) introduced a similarity metric based on Kolmogorov complexity. It followed work by Shannon in the 1950s on a metric based on entropy. We define…

cs.FL2022

Maximal automatic complexity and context-free languages

Bjørn Kjos-Hanssen

Let $A_{N}$ denote nondeterministic automatic complexity and \[ L_{k,c}=\{x\in [k]^* : A_N(x)> |x|/c\}. \] In particular, $L_{k, 2}$ is the language of all $k$ -ary words for which $A_…

math.LO2022

Strong Medvedev reducibilities and the KL-randomness problem

Bjørn Kjos-Hanssen, David J. Webb

While it is not known whether each real that is Kolmogorov-Loveland random is Martin-Löf random, i.e., whether $KLR \subseteq MLR$ , Kjos-Hanssen and Webb (2021) sho…

math.MG2021

Interpolating between the Jaccard distance and an analogue of the normalized information distance

Bjørn Kjos-Hanssen

Jiménez, Becerra, and Gelbukh (2013) defined a family of "symmetric Tversky ratio models" $S_{α, β}$ , $0 \leq α \leq 1$ , $β > 0$ . Each function $D_{α, β} = 1 - S_{α, β}$ is a semimetric on the p…

math.LO2021

KL-randomness and effective dimension under strong reducibility

Bjørn Kjos-Hanssen, David J. Webb

We show that the (truth-table) Medvedev degree KLR of Kolmogorov--Loveland randomness coincides with that of Martin Löf randomness, MLR, answering a question of Miyabe. Next, an an…

math.LO2021

On the degrees of constructively immune sets

Samuel D. Birns, Bjørn Kjos-Hanssen

Xiang Li (1983) introduced what are now called constructively immune sets as an effective version of immunity. Such have been studied in relation to randomness and minimal indices,…

cs.DM2020

Automatic complexity of Fibonacci and Tribonacci words

Bjørn Kjos-Hanssen

For a complexity function $C$ , the lower and upper $C$ -complexity rates of an infinite word $x$ are \[ \underline{C}(\mathbf x)=\liminf_{n\to\infty} \frac{C(\mathbf{x}\uph…

math.LO2020

A conflict between some semantic conditions of Carmo and Jones for contrary-to-duty obligations

Bjørn Kjos-Hanssen

We show that Carmo and Jones' condition 5(e) conflicts with the other conditions on their models for contrary-to-duty obligations. We then propose a resolution to the conflict.

math.LO2020★ 1 cited

From eventually different functions to pandemic numberings

Achilles A. Beros, Mushfeq Khan, Bjørn Kjos-Hanssen +1

A function is strongly non-recursive (SNR) if it is eventually different from each recursive function. We obtain hierarchy results for the mass problems associated with computing s…

cs.FL2020

VC-dimensions of nondeterministic finite automata for words of equal length

Bjørn Kjos-Hanssen, Clyde James Felix, Sun Young Kim +2

Let $N F A_{b} (q)$ denote the set of languages accepted by nondeterministic finite automata with $q$ states over an alphabet with $b$ letters. Let $B_{n}$ denote the set of words of leng…

cs.FL2019

An incompressibility theorem for automatic complexity

Bjørn Kjos-Hanssen

Shallit and Wang showed that the automatic complexity $A (x)$ satisfies $A (x) \geq n /13$ for almost all $x \in {0, 1}^{n}$ . They also stated that Holger Petersen had…

math.LO2019

A tractable case of the Turing automorphism problem: bi-uniformly $E_{0}$ -invariant Cantor homeomorphisms

Bjørn Kjos-Hanssen

A function $F : 2^{ω} \to 2^{ω}$ is an $E_{0}$ -isomorphism if for all $x, y \in 2^{ω}$ , we have $x E_{0} y ⟺ f (x) E_{0} f (y)$ , where $x E_{0} y ⟺ (\exists a) (\forall n \geq b) x (n) = y (n)$ . If such witness…

cs.FL2019

Planar digraphs for automatic complexity

Achilles A. Beros, Bjørn Kjos-Hanssen, Daylan Kaui Yogi

We show that the digraph of a nondeterministic finite automaton witnessing the automatic complexity of a word can always be taken to be planar. In the case of total transition func…

cs.FL2019

The number of languages with maximum state complexity

Bjørn Kjos-Hanssen, Lei Liu

Câmpeanu and Ho (2004) determined the maximum finite state complexity of finite languages, building on work of Champarnaud and Pin (1989). They stated that it is very difficult to…

math.LO2017

Covering the recursive sets

Bjørn Kjos-Hanssen, Frank Stephan, Sebastiaan A. Terwijn

We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct c…

cs.CR2017

Superposition as memory: unlocking quantum automatic complexity

Bjørn Kjos-Hanssen

Imagine a lock with two states, "locked" and "unlocked", which may be manipulated using two operations, called 0 and 1. Moreover, the only way to (with certainty) unlock using four…

math.LO2016★ 1 cited

Effective bi-immunity and randomness

Achilles A. Beros, Mushfeq Khan, Bjørn Kjos-Hanssen

We study the relationship between randomness and effective bi-immunity. Greenberg and Miller have shown that for any oracle X, there are arbitrarily slow-growing DNR functions rela…

cs.FL2016

Few paths, fewer words: model selection with automatic structure functions

Bjørn Kjos-Hanssen

We consider the problem of finding an optimal statistical model for a given binary string. Following Kolmogorov, we use structure functions. In order to get concrete results, we re…

cs.LO2016★ 2 cited

Models of the Chisholm set

Bjørn Kjos-Hanssen

We give a counter-example showing that Carmo and Jones' condition 5(e) may conflict with other conditions on the models in their paper \emph{A new approach to contrary-to-duty obli…

Quantum Černý complexity of binary words

The exact asymptotic constant in the metric dimension of Jaccard space

Exact versus unique nondeterministic automatic complexity

Every string has probabilistic automatic complexity at most three

Languages of Words of Low Automatic Complexity Are Hard to Compute

Conditional automatic complexity and its metrics

Maximal automatic complexity and context-free languages

Strong Medvedev reducibilities and the KL-randomness problem

Interpolating between the Jaccard distance and an analogue of the normalized information distance

KL-randomness and effective dimension under strong reducibility

On the degrees of constructively immune sets

Automatic complexity of Fibonacci and Tribonacci words

A conflict between some semantic conditions of Carmo and Jones for contrary-to-duty obligations

From eventually different functions to pandemic numberings

VC-dimensions of nondeterministic finite automata for words of equal length

An incompressibility theorem for automatic complexity

A tractable case of the Turing automorphism problem: bi-uniformly E0​-invariant Cantor homeomorphisms

Planar digraphs for automatic complexity

The number of languages with maximum state complexity

Covering the recursive sets

Superposition as memory: unlocking quantum automatic complexity

Effective bi-immunity and randomness

Few paths, fewer words: model selection with automatic structure functions

Models of the Chisholm set

A tractable case of the Turing automorphism problem: bi-uniformly $E_{0}$ -invariant Cantor homeomorphisms