The 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. We have made some unsuccessful attempts at writing programs that solve it.)

The 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. We have made some unsuccessful attempts at writing programs that solve it.)

The 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 $G$ is the homomorphic image of $B_n$ for some $n$.

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. We have made some unsuccessful attempts at writing programs that solve it.)

The 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. We have made some unsuccessful attempts at writing programs that solve it.)

The 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 $G$ is the homomorphic image of $B_n$ for some $n$.

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$.

(We came upon this problem via an open problem in logic, see also our recent abstract.)

The 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 $G$ is the homomorphic image of $B_n$ for some $n$.

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. We have made some unsuccessful attempts at writing programs that solve it.)