BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Bjørn Kjos-Hanssen

Bjørn Kjos-Hanssen contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.LOFormal Languages and Automata Theorymath.COLogic in Computer Science

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

An incompressibility theorem for automatic complexity

Shallit and Wang showed that the automatic complexity $A(x)$ satisfies $A(x)\ge n/13$ for almost all $x\in{\{\mathtt{0},\mathtt{1}\}}^n$. They also stated that Holger Petersen had informed them that the constant 13 can be reduced to 7. Here we show that it can be reduced to $2+ε$ for any $ε>0$. The result also applies to nondeterministic automatic complexity $A_N(x)$. In that setting the result is tight inasmuch as $A_N(x)\le n/2+1$ for all $x$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Maximal automatic complexity and context-free languages

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_N$ is maximal, while $L_{k,3}$ gives a rough dividing line between complex and simple. Let $\mathbf{CFL}$ denote the complexity class consisting of all context-free languages. While it is not known that $L_{2,2}$ is infinite, Kjos-Hanssen (2017) showed that $L_{3,2}$ is $\mathbf{CFL}$-immune but not $\mathbf{coCFL}$-immune. We complete the picture by showing that $L_{3,2}\not\in\mathbf{coCFL}$. Turning to Boolean circuit complexity, we show that $L_{2,3}$ is $\mathbf{SAC}^0$-immune and $\mathbf{SAC}^0$-coimmune. Here $\mathbf{SAC}^0$ denotes the complexity class consisting of all languages computed by (non-uniform) constant-depth circuits with semi-unbounded fanin. As for arithmetic circuits, we show that $\{x:A_N(x)>1\}\not\in\oplus\mathbf{SAC}^0$. In particular, $\mathbf{SAC}^0\not\subseteq\oplus \mathbf{SAC}^0$, which resolves an open implication from the Complexity Zoo.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Strong Medvedev reducibilities and the KL-randomness problem

While it is not known whether each real that is Kolmogorov-Loveland random is Martin-Löf random, i.e., whether $\mathrm{KLR}\subseteq\mathrm{MLR}$, Kjos-Hanssen and Webb (2021) showed that $\mathrm{MLR}$ is truth-table Medvedev reducible ($\le_{s,tt}$) to $\mathrm{KLR}$. They did this by studying a natural class Either(MLR) and showing that $\mathrm{MLR}\le_{s,tt}\mathrm{Either(MLR)}\supseteq\mathrm{KLR}$. We show that Degtev's stronger reducibilities (positive and linear) do not suffice for the reduction of MLR to Either(MLR), and some related results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A tractable case of the Turing automorphism problem: bi-uniformly $E_0$-invariant Cantor homeomorphisms

A function $F:2^ω\to 2^ω$ is an $E_0$-isomorphism if for all $x,y\in 2^ω$, we have $xE_0y\iff f(x)E_0 f(y)$, where $xE_0y\iff(\exists a)(\forall n\ge b) x(n)=y(n)$. If such witnesses $a$ for $xE_0 y$ and for $f(x)E_0 f(y)$ depend on each other but not on $x$, $y$, then $F$ is called bi-uniform. It is shown that a homeomorphism of Cantor space which is a bi-uniform $E_0$-isomorphism can induce only the trivial automorphism of the Turing degrees.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Automatic complexity of shift register sequences

Let $x$ be an $m$-sequence, a maximal length sequence produced by a linear feedback shift register. We show that $x$ has maximal subword complexity function in the sense of Allouche and Shallit. We show that this implies that the nondeterministic automatic complexity $A_N(x)$ is close to maximal: $n/2-A_N(x)=O(\log^2n)$, where $n$ is the length of $x$. In contrast, Hyde has shown $A_N(y)\le n/2+1$ for all sequences $y$ of length $n$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

From eventually different functions to pandemic numberings

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 such functions with varying growth bounds. In particular, there is no least and no greatest Muchnik degree among those of the form SNR$_f$ consisting of SNR functions bounded by varying recursive bounds $f$. We show that the connection between SNR functions and canonically immune sets is, in a sense, as strong as that between DNR (diagonally non-recursive) functions and effectively immune sets. Finally, we introduce pandemic numberings, a set-theoretic dual to immunity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Nondeterministic automatic complexity of overlap-free and almost square-free words

Shallit and Wang studied deterministic automatic complexity of words. They showed that the automatic Hausdorff dimension $I(\mathbf t)$ of the infinite Thue word satisfies $1/3\le I(\mathbf t)\le 2/3$. We improve that result by showing that $I(\mathbf t)\ge 1/2$. For nondeterministic automatic complexity we show $I(\mathbf t)=1/2$. We prove that such complexity $A_N$ of a word $x$ of length $n$ satisfies $A_N(x)\le b(n):=\lfloor n/2\rfloor + 1$. This enables us to define the complexity deficiency $D(x)=b(n)-A_N(x)$. If $x$ is square-free then $D(x)=0$. If $x$ almost square-free in the sense of Fraenkel and Simpson, or if $x$ is a strongly cube-free binary word such as the infinite Thue word, then $D(x)\le 1$. On the other hand, there is no constant upper bound on $D$ for strongly cube-free words in a ternary alphabet, nor for cube-free words in a binary alphabet. The decision problem whether $D(x)\ge d$ for given $x$, $d$ belongs to $NP\cap E$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the complexity of automatic complexity

Generalizing the notion of automatic complexity of individual strings due to Shallit and Wang, we define the automatic complexity $A(E)$ of an equivalence relation $E$ on a finite set $S$ of strings. We prove that the problem of determining whether $A(E)$ equals the number $|E|$ of equivalence classes of $E$ is $\mathsf{NP}$-complete. The problem of determining whether $A(E) = |E| + k$ for a fixed $k\ge 1$ is complete for the second level of the Boolean hierarchy for $\mathsf{NP}$, i.e., $\mathsf{BH}_2$-complete. Let $L$ be the language consisting of all strings of maximal nondeterministic automatic complexity. We characterize the complexity of infinite subsets of $L$ by showing that they can be co-context-free but not context-free, i.e., $L$ is $\mathsf{CFL}$-immune, but not $\mathsf{coCFL}$-immune. We show that for each $ε>0$, $L_ε\not\in\mathsf{coCFL}$, where $L_ε$ is the set of all strings whose deterministic automatic complexity $A(x)$ satisfies $A(x)\ge |x|^{1/2-ε}$.

0 citations0 reviewsNo code linkedOpen access