The [De Bruijn graph](https://en.wikipedia.org/wiki/De_Bruijn_graph) $B_n$ of
dimension $n$ (on the two-letter alphabet) is defined as the directed graph on
$2^n$ vertices and $2^{n+1}$ edges, where for every $w = w_0 \dots w_n \in
2^{n+1}$ we put an edge from the vertex $w_0 \dots w_{n-1}$ to the vertex $w_1
\dots w_n$. For the purposes of our problem, the edges are also $2$-colored,
where the color of the edge determined by $w \in 2^{n+1}$ is $w_0$.

Given a finite directed graph $G$ with a $2$-coloring on the edges, we ask
whether or not there exist $n$ and a homomorphism from $B_n$ to $G$.

Is this problem decidable? That is, is there an algorithm which, given such a
$G$, answers "yes" if and only if there exist $n$ and a homomorphism $B_n \to
G$, and "no" otherwise?

Here, a homomorphism is required to preserve the $2$-coloring on edges.
Formally, a homomorphism from $B_n$ to $G$ is a function $f \colon 2^n \to
V(G)$ such that for every edge $(u,v)$ of color $b$, $(f(u), f(v))$ is an edge
in $G$ of color $b$.

An equivalent formulation of a more topological, dynamical-systems flavor is the following: Given a finite directed graph $G$ with a $2$-coloring on edges, decide whether or not there exists a continuous function $f$ from Cantor space $2^\omega$ to $V(G)$ such that, for every $u \in 2^\omega$, $(f(u), f(u'))$ is an edge of color $u_0$, where $u' := u_1 u_2 \dots$, the tail of $u$, and the finite set $V(G)$ has the discrete topology.

(We came upon this problem via an open problem in logic, see also our [recent
abstract](https://inria.hal.science/hal-04128087/file/UNIF_2023_paper_5.pdf). We have made some [unsuccessful attempts](https://github.com/johannesmarti/dbg) at writing programs that solve it.)