76 citations · 440 across the 53 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.FL2022
Maximal automatic complexity and context-free languages
Bjørn Kjos-Hanssen
Let denote nondeterministic automatic complexity and \[ L_{k,c}=\{x\in [k]^* : A_N(x)> |x|/c\}. \] In particular, is the language of all -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 , Kjos-Hanssen and Webb (2021) sho…