9
$\begingroup$

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

$\endgroup$
6
  • 3
    $\begingroup$ Your "that is" statement of decidability is incorrect, since you only state the positive requirement. This defines semi-decidability, and indeed your problem is semi-decidable, since we can just search for an $n$ and say Yes when (and if) we find one for which there is a homomorphism using that $B_n$. This will fulfill your "that is" statement, and shows that the problem is computably enumerable (semi-decidable). But decidability should also mean that you say No if and only if there is no such homomorphism. That is, you want the decision procedure to terminate with Yes or No in finite time. $\endgroup$ Aug 11, 2023 at 15:04
  • 1
    $\begingroup$ Thanks, you're right, I added "and "no" otherwise" just to be sure... $\endgroup$
    – Sam van G
    Aug 11, 2023 at 15:06
  • 1
    $\begingroup$ My first guess is that this is decidable, with a "first periodic and aperiodic points, then transitions" type argument, similar to the proofs of the factor/embedding theorems (of symbolic dynamics). $\endgroup$
    – Ville Salo
    Aug 11, 2023 at 17:08
  • 2
    $\begingroup$ Only somewhat related, but counting the number of homomorphic images of de Bruijn graphs is a very difficult problem (see §6 of arXiv:2004.08478). Perhaps some useful ideas can be found in there. $\endgroup$ Aug 12, 2023 at 7:41
  • 1
    $\begingroup$ @SamvanG No problem. And of course -- welcome to MO, Sam, it's nice to see you here! :) $\endgroup$ Aug 12, 2023 at 11:04

4 Answers 4

8
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ Thank you! We need to study this a bit, and we hope we may ask some clarification questions if needed. $\endgroup$
    – Sam van G
    Aug 13, 2023 at 6:57
  • 1
    $\begingroup$ 3) We can define the homomorphism recursively by mapping all zeros to $v_0$ and then for every string $s$ we have already mapped choosing edges to correspond to $s \rightarrow s[1..n-1]0$ and $s \rightarrow s[1..n-1]1$. We then need to make sure this map is surjective and well defined (the same string always gets mapped to the same vertex). For the choice of edge we do the following in decreasing order of precedence: $\endgroup$
    – 1001
    Aug 13, 2023 at 10:23
  • 2
    $\begingroup$ 1. If the first $n - \ell$ letters are zeros, then follow the chosen path. 2. Otherwise, if the string has a "long" suffix with a "short" period, we go to the corresponding cycle. 3. Otherwise, if a "local maximum" passes a certain position in the string we start following the length $m$ path given by $H'$ (for each edge $(u', v')$ in $H'$ and $u \in u'$ we choose a fixed $v \in v'$ such that $(u, v) \in G$). 4. Otherwise we can just follow the edges in the singleton layer of $H'$. $\endgroup$
    – 1001
    Aug 13, 2023 at 10:27
  • 1
    $\begingroup$ 1) No, I don't think so. New letters are added on the right, shifting the old letters to the left. This must be mapped to a forward edge in G. $\endgroup$
    – 1001
    Aug 13, 2023 at 10:30
  • 1
    $\begingroup$ I see now. Yes I mean the colour of the new letter on the right. Sorry for the confusion. $\endgroup$
    – 1001
    Aug 13, 2023 at 17:09
6
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Thanks for this! First, you’re right that it was ambiguous, we strictly speaking only need to decide whether or not there exists a homomorphism, but typically think about deciding the existence of surjections (which clearly suffices - not completely sure about the other direction though so I edited the question to be less ambiguous). $\endgroup$
    – Sam van G
    Aug 12, 2023 at 7:12
  • 1
    $\begingroup$ For the remainder of your comments, we will need a while to think about it and read your work. It would be great if these methods can help solve it. $\endgroup$
    – Sam van G
    Aug 12, 2023 at 7:14
  • $\begingroup$ Looking at the proof of your Theorem 1, I think that, in the setting of our given graph $G$, "suitably repeatable part" could mean the following: for any finite word $w \in 2^*$, write $H(w)$ for the relation on vertices of $G$ defined by $u H(w) v$ iff there is a path in $G$ from $u$ to $v$ labeled by $w$. Then a finite factor $w$ of $y \in 2^\omega$ is suitable if $H(w)$ is an idempotent relation. Does that fit with your intuitions? $\endgroup$
    – Sam van G
    Aug 12, 2023 at 14:19
  • 1
    $\begingroup$ Yeah, this agrees with my intuition. But I haven't done an argument of this type in the one-sided setting, so I'm not sure on the details of consistently picking which part is repeated. $\endgroup$
    – Ville Salo
    Aug 12, 2023 at 14:38
4
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ It precisely seemed to me that the one-sided version doesn't allow a simple periodic point condition, since you cannot look both ways and thus it's hard to know where you should go at each moment... I only believed that the "recursive bound on radius from simplifying an existing section by imagining repeated cycles to the right" type argument (which is what we use in the general sofic case also in the two-sided setting) might adapt. Anyway hopefully 1001's answer is correct, and this doesn't matter. $\endgroup$
    – Ville Salo
    Aug 14, 2023 at 10:30
  • 1
    $\begingroup$ Thanks again for the references and pointing out the connection to your papers! We might have to look whether we can adapt these results to the "one-sided" case, in case the other approach does not work out. $\endgroup$
    – no_hurry
    Aug 14, 2023 at 15:45
  • 2
    $\begingroup$ We once also proved with Thibault Godin that splic epicness is decidable for certain automata semigroups, if you like I can send you that too. (Like one-sided automorphisms of full shifts, automata groups act on trees, so a priori seems relevant.) Though that also seems quite different from your case. But maybe check 1001's first. $\endgroup$
    – Ville Salo
    Aug 14, 2023 at 16:05
1
$\begingroup$

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

New contributor
Miroslav Olšák is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.