76 citations · 440 across the 53 of their papers we have counts for
14 papers · 1 filter
Exact versus unique nondeterministic automatic complexity
Bjørn Kjos-Hanssen, Travis Rivera Petit
The exact nondeterministic automatic complexity of a word is the minimum number of states of a nondeterministic finite automaton that accepts and no other word…
Every string has probabilistic automatic complexity at most three
Bjørn Kjos-Hanssen
Gill (arXiv:2402.13376) introduced the probabilistic automatic complexity of a finite string : the least number of states of a probabilistic finite automaton (PFA) for…
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…
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…
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_…
VC-dimensions of nondeterministic finite automata for words of equal length
Bjørn Kjos-Hanssen, Clyde James Felix, Sun Young Kim +2
Let denote the set of languages accepted by nondeterministic finite automata with states over an alphabet with letters. Let denote the set of words of leng…
An incompressibility theorem for automatic complexity
Bjørn Kjos-Hanssen
Shallit and Wang showed that the automatic complexity satisfies for almost all . They also stated that Holger Petersen had…
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…
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…
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…
Automatic complexity of shift register sequences
Bjørn Kjos-Hanssen
Let be an -sequence, a maximal length sequence produced by a linear feedback shift register. We show that has maximal subword complexity function in the sense of Allouch…
On the complexity of automatic complexity
Bjørn Kjos-Hanssen
Generalizing the notion of automatic complexity of individual strings due to Shallit and Wang, we define the automatic complexity of an equivalence relation on a finite…
Kolmogorov structure functions for automatic complexity
Bjørn Kjos-Hanssen
For a finite word we define and study the Kolmogorov structure function for nondeterministic automatic complexity. We prove upper bounds on that appear to be quite…
Nondeterministic automatic complexity of overlap-free and almost square-free words
Kayleigh Hyde, Bjørn Kjos-Hanssen
Shallit and Wang studied deterministic automatic complexity of words. They showed that the automatic Hausdorff dimension of the infinite Thue word satisfies $1/3\le…