76 citations · 440 across the 53 of their papers we have counts for
4 papers · 1 filter
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…
A tractable case of the Turing automorphism problem: bi-uniformly -invariant Cantor homeomorphisms
Bjørn Kjos-Hanssen
A function is an -isomorphism if for all , we have , where . If such witness…
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…