Deciding homomorphic images of De Bruijn graphs

Question

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

Answer 1

Yes, the problem is decidable. We give a (very slow) algorithm for checking if there exists a surjective homomorphism to $G$. This implies the result for genereal homomorphisms by checking all subgraphs of $G$.

It is easy to see that the following properties are necessary:

I There is a vertex in $G$ which is reachable from every other vertex using only 0-edges.

II There is a vertex in $G$ which is reachable from every other vertex using only 1-edges.

III $G$ is strongly connected.

However these conditions are not sufficient.

First note that when traversing the de Bruijn graph $B_n$, the current state will be forgotten after processing $n$ letters. In automaton language, $\delta(v, s) = \delta(u, s)$ for all vertices $u, v$ of $B_n$ and every word $s \in \Sigma^{\geq n}$. Let's call this property $n$-forgetful (I would imagine this has a name, but I cannot think of it).

Note that this property is very important, since we can reformulate the problem as does there exist a homomorphism from all left infinite strings to $V$ such that all strings with the same length $n$ suffix get sent to the same vertex, i.e. everything is forgotten after $n$ steps.

The $n$-forgetfulness property also implies that for any $s \in \Sigma^{\geq n}$ there must be paths starting at every vertex in $V$ and by following edges corresponding to the colours of $s$ all end up at the same vertex.

Now consider a graph $H = (V', A')$ where every vertex corresponds to a non-empty subset of $V$, i.e. $V' = \mathcal{P}(V) \setminus \emptyset$. We put an edge in colour $c$ from $u'$ to $v'$ if every vertex in $u'$ has an edge in colour $c$ to a vertex in $v'$. Now consider the following question:

Does there exist a subgraph of $H$ on the same set of vertices such that every vertex has exactly one outgoing edge in each colour such that all recurrent vertices correspond to single element subsets in $V$?

Note that this question is decidable (You can start with the single-vertex subsets and add other subsets one by one if they have a 0-edge and a 1-edge to existing subsets.) and needs to be answered positively for the forgetfulness property to hold.

Now suppose such a subgraph $H'$ exists. We pick a vertex satisfying (I) and call it $v_0$. Similarly we pick a vertex $v_1$ satisfying (II). Note that we can pick $H'$ such that $v_0$ is the unique sink of the subgraph obtained by taking all 0-edges from $H'$, while $v_1$ is the unique sink when taking all the 1-edges.

By considering the paths starting at the vertex $V \in V'$, we can observe that this corresponds to an algorithm forget the current state in $m$ steps, where $m$ can be chosen to be any number at least the length of the longest path to a single-vertex state. We want to use this algorithm to ensure $n$-forgetfulness. However, the problem is that if two strings become equal, they have to start this forgetting process at the same time.

To do this we to use properties which are sort of invariant under small translations such as minimizers/maximizers. In highly periodic strings minima/maxima are not really well defined, but then we can use periodicity instead.

We (re)start the forgetting algorithm (which decides where to go in $G$ during the next $m$ steps) if the length $9m$ suffix is the lexicographically greatest suffix of the length $10m$ suffix. Now as more letters are added at the information of the original state gets lost, unless we restart the algorithm within $m$ steps. This can have two causes:

• the suffixes get greater and greater lexicographically: this cannot continue indefinitely, because there are only a finite number of possible suffixes, namely $2^{10m+1} - 1$.

• the suffix is periodic with period smaller than $m$.

To take care of the periodic case we do the following to forget:

If the suffix of length $20m$ is periodic with period at most $m$, we consider the smallest period $p$. For every string $s$ of length $< m$ (up to cyclic permutation) which is not a power we check if there exists a cycle in $G$ corresponding to $s$ and if we can reach from all vertices using a path of the colours of $s^k$ (note that this is decidable). Let $K$ be the greatest necessary $k$. If the suffix of length $20m$ is periodic with smallest period at most $m$ we go to the corresponding cycle instead and do not start the forgetting algorithm.

Note that by picking $n \geq 2^{10m+1} \cdot 20m \cdot K$ we can ensure forgetfulness.

We still need to ensure that $f$ is surjective. We can do this by constructing a path starting at $v_0$ which visits all edges and taking its corresponding string $s$. Without loss of generality we can start it with a 1-edge. We call the length of this path $\ell$ and map all strings of the form $0^{n + 1 - i}s[0..i]$ according to this path. Thus we want to pick $m > \ell$.

Since we just care about the decision problem, it suffices to check conditions I, II, III and

IV $H$ has such a subgraph $H'$. (You can start with the single-vertex subsets and add other subsets one by one if they have a 0-edge and a 1-edge to existing subsets.)

V For every string of length at most $m$, there exists a cycle corresponding to that string and we can reach this cycle from any vertex using a power of the string.

Answer 2

I'm on vacation, but just a few quick thoughts. First, "we ask whether or not $G$ is the homomorphic image of $B_n$ for some $n$." sounds like you want a surjection, but the other parts of your question (and your article) suggest to me that you don't need a surjection, though I'm not completely sure. I will interpret the question as not requiring a surjection. (Though similar ideas may be relevant if you want a surjection.)

I think symbolic dynamically your problem can be restated as follows: take $X \subset E(G)^{\mathbb{N}}$ to be the edge shift defined by the graph (i.e. the sets of sequences of edges on one-way infinite paths), and $Y = \{0,1\}^{\mathbb{N}}$ the binary full shift. Let $\phi : X \to Y$ be the map that writes down the labels written on the edges. It is a block map, i.e. shift commuting and continuous. You are asking whether it is decidable whether it has a section meaning a shift-commuting continuous map $\psi : Y \to X$ such that $\phi \circ \psi = \mathrm{id}_Y$. The window size of this block map (how many symbols it reads the determine the symbol to write) corresponds to the number $n$ (or maybe $n+1$ since you map to vertices).

In other words, we are asking if this $\phi$ is split epic in the category of subshifts (with subshifts as objects, and block maps as morphisms). Slightly generalizing, we can ask whether, given a block map between sofic shifts (or just subshifts of finite type if you prefer), split epicness is decidable.

In [1] we studied this question with Ilkka Törmä, in the cousin category of two-sided subshifts. We showed that for block maps between two sofic shifts, if there is a section, then there is a section of recursively bounded radius. Furthermore, in the case of subshifts of finite type (like in your situation), the existence of a section amounts to a "periodic point condition", i.e. in a sense you just have to check that there is no "obvious obstacle" to the existence of a section, coming from a finite set of periodic points. (Although in this case the obvious obstacle is not the most obvious one.) I applied a variant of this algorithm in [2], so you can find some practical discussion there.

Now, typically in symbolic dynamics, one-sided questions are easier: some things whose decidability is open in the two-sided case have known decision algorithms in the one-sided case, and usually in the two-sided case we have more complicated phenomena in general. This perhaps explains my intuition from yesterday's comment.

In this particular case, however, it looks like two-sidedness is actually helping us, since the construction of a section is easier because you can look both ways...

The idea in [1] is something like this. Let $\psi : X \to Y$ be a section for $\phi$. We want to give a recursive upper bound on its radius. We want to modify $\psi$ to get another section $\psi'$ with bounded radius. The idea is that $\psi'(y)$ is built by replacing some parts of $y$ by "infinite repetitions", and then applying $\psi$ to the resulting configuration. This means that $\psi'$ will have bounded radius if there are suitably repeatable parts in $y$ sufficiently often, since it doesn't look over those parts to pick images.

To get the suitably repeatable parts, we use the most basic Ramsey theorem (but I think you can also use e.g. the ergodic theorem) to find that every configuration has long suitably repetitive parts. I don't immediately see what "suitably" means in your case, however.

References

[1] Salo, Ville; Törmä, Ilkka, Category theory of symbolic dynamics, Theor. Comput. Sci. 567, 21-45 (2015). ZBL1314.37011.

[2] Salo, Ville. "On von Neumann regularity of cellular automata." Natural Computing (2023): 1-12., https://link.springer.com/content/pdf/10.1007/s11047-022-09935-w.pdf

Answer 3

Many thanks for your suggestions! I am Sam's coauthor, but first need to gain some reputation to comment directly on your replies.

In our previous attempts at solving the problem, we came accross a particular graph, which indicates that a path/cycle-based condition (such as one-sided versions of the periodic point condition suggested by Ville Salo) is not sufficient. The graph $G = (V,R_0,R_1)$ (we call it the "Hamburger") is as follows:

1. $V = \{a,b,c\}$,
2. $R_0 = \{(a,a), (a,c), (c,a), (c,b), (b,c), (b,a)\} = (V \times V) \setminus \{(a,b), (c,c), (b,b)\}$, and
3. $R_1 = \{(b,b), (b,c), (c,b), (c,a), (a,c), (a,b)\} = (V \times V) \setminus \{(b,a), (c,c), (a,a)\}$.

In this graph all sorts of cycles exist and for sufficiently long words there are paths between any two vertices: Writing $R_w = R_{w_1} \circ \dots \circ R_{w_n}$ for a word $w = w_1 \dots w_n$, we get that:

1. $R_{00} = R_{10} = (V \times V) \setminus \{(c,b)\}$,
2. $R_{11} = R_{01} = (V \times V) \setminus \{(c,a)\}$, and
3. $R_w = V \times V$ for every $w$ with $|w| \geq 3$.

One can show that there is no surjective homomorphism $B_n \to G$ for any $n$. One strategy is to observe that there is no subgraph of the kind mentioned by 1001 in their reply. Starting from the singletons $\{a\}$, $\{c\}$ and $\{b\}$ one can reach $\{a,b\}$ from $\{c\}$ via both a $0$ and a $1$-edge. But then one is stuck and no additional subsets can be connected to the singleton part.

Answer 4

This is quite relevant to my article Local Loop Lemma. I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph which is strongly connected and has directed walks of all lengths is a homomorphic image of a De Bruijn graph without loops -- see sections 3.1, 3.2 in the article.

To comment how the construction in the article differs from your question:

1. I only needed a homomorphism to exist (with certain properties), not necessarily it to be surjective. On the other hand, the construction in the paper had enough of freedom to be able to be modified to a surjective one.
2. The paper works with De Bruijn graph without loops. When loops are included, the condition simplifies even more: G is an image of a De Bruijn graph if and only if it is strongly connected, and contains a loop.

Whether a graph is strongly connected and has a loop is decidable in linear time. :-)

Edit: Just later, I have noticed that the question is about graphs that have 2-colored edges, which was not the case in Local Loop Lemma. Then I am actually not sure if there is a simple characterization of images of De Bruijn graphs... (I can think about it)