Return to Answer

Here is a second answer that is just rephrasing @DerekHolt’s answer based on the comments. So upvote his answer first! Let $X$ be a finite alphabet. An inverse automaton is a finite directed graph labeled over the alphabet $X$ which is folded in the sense of Stallings, meaning you cannot find two edges entering or leaving a vertex with the same label. Equivalently these are immersions over a bouquet of circles. An inverse automaton has a unique initial state and a set of final states. It recognizes a subset of the free group by looking at all reduced words labelling a path from the initial state to a final state, where inverse letters read edges backward. The language accepted by an inverse automaton is a finite union of cosets of finitely generated subgroups.

The languages accepted by inverse automata are closed under intersection. You simply build the product automaton whose vertices are pairs of vertices and there is an edge labeled by $x$ from $(p,q)$ to $(p’,q’)$ if and only if there are edges from $p$ to $p’$ and $q$ to $q’$ labeled by $x$. This construction is the fiber product of the two inverse automata viewed as immersions over a bouquet of circles. The initial state is the pair of initial states and the final states are those pairs $(p,q)$ where both $p$ and $q$ are final in their respective automata. This is an inverse automata that will accept precisely those reduced words which both automata accept. In particular, the intersection is empty iff the initial vertex of the product construction cannot reach any terminal vertex.

Now to recognize $Hw$ write a linear automaton reading the word $w$ (with inverse letters read backward) and attach at the initial point a generating set for $H$ as loops and apply Stallings foldings. The initial vertex is the intial vertex of $w$ and the final vertex is the end point of $w$. These may collapse after folding.

We can do a similar thing for $gK$, but we put the generators of $K$ as loops at the end of the path labelled $g$, and then to test if $w\in HgK$ we just form the product automaton for $Hw$ and $gK$ and check if the final state is reachable from the initial state.

Note $w=hgk$ iff $h^{-1}w=gk$. So $Hw$ and $gK$ intersect iff $w\in HgK$.

Here is a second answer that is just rephrasing @DerekHolt’s answer based on the comments. So upvote his answer first! Let $X$ be a finite alphabet. An inverse automaton is a finite directed graph labeled over the alphabet $X$ which is folded in the sense of Stallings, meaning you cannot find two edges entering or leaving a vertex with the same label. Equivalently these are immersions over a bouquet of circles. An inverse automaton has a unique initial state and a set of final states. It recognizes a subset of the free group by looking at all reduced words labelling a path from the initial state to a final state, where inverse letters read edges backward. The language accepted by an inverse automaton is a finite union of cosets of finitely generated subgroups.

The languages accepted by inverse automata are closed under intersection. You simply build the product automaton whose vertices are pairs of vertices and there is an edge labeled by $x$ from $(p,q)$ to $(p’,q’)$ if and only if there are edges from $p$ to $p’$ and $q$ to $q’$ labeled by $x$. This construction is the fiber product of the two inverse automata viewed as immersions over a bouquet of circles. The initial state is the pair of initial states and the final states are those pairs $(p,q)$ where both $p$ and $q$ are final in their respective automata. This is an inverse automata that will accept precisely those reduced words which both automata accept. In particular, the intersection is empty iff the initial vertex of the product construction cannot reach any terminal vertex.

Now to recognize $Hw$ write a linear automaton reading the word $w$ (with inverse letters read backward) and attach at the initial point a generating set for $H$ as loops and apply Stallings foldings. The initial vertex is the intial vertex of $w$ and the final vertex is the end point of $w$. These may collapse after folding. This is essentially the Stallings core of $H$ with a thorn labeled $w$ sticking out of the base point and Stallings uses this automaton in his proof of Marshall Hall's Theorem.

We can do a similar thing for $gK$, but we put the generators of $K$ as loops at the end of the path labelled $g$, and then to test if $w\in HgK$ we just form the product automaton for $Hw$ and $gK$ and check if the final state is reachable from the initial state.

Note $w=hgk$ iff $h^{-1}w=gk$. So $Hw$ and $gK$ intersect iff $w\in HgK$.

Here is a second answer that is just rephrasing @DerekHolt’s answer based on the comments. So upvote his answer first! Let $X$ be a finite alphabet. An inverse automaton is a finite directed graph labeled over the alphabet $X$ which is folded in the sense of Stallings, meaning you cannot find two edges entering or leaving a vertex with the same label. An inverse automaton has a unique initial state and a set of final states. It recognizes a subset of the free group by looking at all reduced words labelling a path from the initial state to a final state, where inverse letters read edges backward. The language accepted by an inverse automaton is a finite union of cosets of finitely generated subgroups.

The languages accepted by inverse automata are closed under intersection. You simply build the product automaton whose vertices are pairs of vertices and there is an edge labeled by $x$ from $(p,q)$ to $(p’,q’)$ if and only if there are edges from $p$ to $p’$ and $q$ to $q’$ labeled by $x$. The initial state is the pair of initial states and the final states are those pairs $(p,q)$ where both $p$ and $q$ are final in their respective automata. This is an inverse automata that will accept precisely those reduced words which both automata accept. In particular, the intersection is empty iff the initial vertex of the product construction cannot reach any terminal vertex.

Now to recognize $Hw$ write a linear automaton reading the word $w$ (with inverse letters read backward) and attach at the initial point a generating set for $H$ as loops and apply Stallings foldings. The initial vertex is the intial vertex of $w$ and the final vertex is the end point of $w$. These may collapse after folding.

We can do a similar thing for $gK$, but we put the generators of $K$ as loops at the end of the path labelled $g$, and then to test if $w\in HgK$ we just form the product automaton for $Hw$ and $gK$ and check if the final state is reachable from the initial state.

Note $w=hgk$ iff $h^{-1}w=gk$. So $Hw$ and $gK$ intersect iff $w\in HgK$.

Here is a second answer that is just rephrasing @DerekHolt’s answer based on the comments. So upvote his answer first! Let $X$ be a finite alphabet. An inverse automaton is a finite directed graph labeled over the alphabet $X$ which is folded in the sense of Stallings, meaning you cannot find two edges entering or leaving a vertex with the same label. Equivalently these are immersions over a bouquet of circles. An inverse automaton has a unique initial state and a set of final states. It recognizes a subset of the free group by looking at all reduced words labelling a path from the initial state to a final state, where inverse letters read edges backward. The language accepted by an inverse automaton is a finite union of cosets of finitely generated subgroups.

The languages accepted by inverse automata are closed under intersection. You simply build the product automaton whose vertices are pairs of vertices and there is an edge labeled by $x$ from $(p,q)$ to $(p’,q’)$ if and only if there are edges from $p$ to $p’$ and $q$ to $q’$ labeled by $x$. This construction is the fiber product of the two inverse automata viewed as immersions over a bouquet of circles. The initial state is the pair of initial states and the final states are those pairs $(p,q)$ where both $p$ and $q$ are final in their respective automata. This is an inverse automata that will accept precisely those reduced words which both automata accept. In particular, the intersection is empty iff the initial vertex of the product construction cannot reach any terminal vertex.

Now to recognize $Hw$ write a linear automaton reading the word $w$ (with inverse letters read backward) and attach at the initial point a generating set for $H$ as loops and apply Stallings foldings. The initial vertex is the intial vertex of $w$ and the final vertex is the end point of $w$. These may collapse after folding.

We can do a similar thing for $gK$, but we put the generators of $K$ as loops at the end of the path labelled $g$, and then to test if $w\in HgK$ we just form the product automaton for $Hw$ and $gK$ and check if the final state is reachable from the initial state.

Note $w=hgk$ iff $h^{-1}w=gk$. So $Hw$ and $gK$ intersect iff $w\in HgK$.

Here is a second answer that is just rephrasing @DerekHolt’s answer based on the comments. So upvote his answer first! Let $X$ be a finite alphabet. An inverse automaton is a finite directed graph labeled over the alphabet $X$ which is folded in the sense of Stallings, meaning you cannot find two edges entering or leaving a vertex with the same label. An inverse automaton has a unique initial state and a set of final states. It recognizes a subset of the free group by looking at all reduced words labelling a path from the initial state to a final state, where inverse letters read edges backward. The language accepted by an inverse automaton is a finite union of cosets of finitely generated subgroups.

The languages accepted by inverse automata are closed under intersection. You simply build the product automaton whose vertices are pairs of vertices and there is an edge labeled by $x$ from $(p,q)$ to $(p’,q’)$ if and only if there are edges from $p$ to $p’$ and $q$ to $q’$ labeled by $x$. The initial state is the pair of initial states and the final states are those pairs $(p,q)$ where both $p$ and $q$ are final in their respective automata. This is an inverse automata that will accept precisely those reduced words which both automata accept. In particular, the intersection is empty iff the initial vertex of the product construction cannot reach any terminal vertex.

Now to recognize $wH$ write a linear automaton reading the word $w$ (with inverse letters read backward) and attach at the end point a generating set for $H$ as loops and apply Stallings foldings. The initial vertex is the intial vertex of $w$ and the final vertex is the end point of $w$. These may collapse after folding.

We can do a similar thing for $gK$ and then to test if $w\in HgK$ we just form the product automaton for $wH$ and $gK$ and check if the final state is reachable from the initial state.

Here is a second answer that is just rephrasing @DerekHolt’s answer based on the comments. So upvote his answer first! Let $X$ be a finite alphabet. An inverse automaton is a finite directed graph labeled over the alphabet $X$ which is folded in the sense of Stallings, meaning you cannot find two edges entering or leaving a vertex with the same label. An inverse automaton has a unique initial state and a set of final states. It recognizes a subset of the free group by looking at all reduced words labelling a path from the initial state to a final state, where inverse letters read edges backward. The language accepted by an inverse automaton is a finite union of cosets of finitely generated subgroups.

The languages accepted by inverse automata are closed under intersection. You simply build the product automaton whose vertices are pairs of vertices and there is an edge labeled by $x$ from $(p,q)$ to $(p’,q’)$ if and only if there are edges from $p$ to $p’$ and $q$ to $q’$ labeled by $x$. The initial state is the pair of initial states and the final states are those pairs $(p,q)$ where both $p$ and $q$ are final in their respective automata. This is an inverse automata that will accept precisely those reduced words which both automata accept. In particular, the intersection is empty iff the initial vertex of the product construction cannot reach any terminal vertex.

Now to recognize $Hw$ write a linear automaton reading the word $w$ (with inverse letters read backward) and attach at the initial point a generating set for $H$ as loops and apply Stallings foldings. The initial vertex is the intial vertex of $w$ and the final vertex is the end point of $w$. These may collapse after folding.

We can do a similar thing for $gK$, but we put the generators of $K$ as loops at the end of the path labelled $g$, and then to test if $w\in HgK$ we just form the product automaton for $Hw$ and $gK$ and check if the final state is reachable from the initial state.

Note $w=hgk$ iff $h^{-1}w=gk$. So $Hw$ and $gK$ intersect iff $w\in HgK$.