Return to Answer

The $n$-forgetfulnes 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.

Does there exist an 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 forgetful property to hold.

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.

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.

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.

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.

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

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

V For every string of length at most $m$, there exists a cycle corresponding to that string.

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.