Timeline for Membership to double cosets in free groups
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 24, 2021 at 14:30 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 1 character in body
|
| Apr 24, 2021 at 14:29 | comment | added | Benjamin Steinberg | Sorry, the previous comment should say $g\neq 1$ | |
| Apr 24, 2021 at 14:21 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 1039 characters in body
|
| Apr 24, 2021 at 14:13 | comment | added | Benjamin Steinberg | I don't assume $g=1$ I use an epsilon transition so the endpoints are different. I had edited it to make that clear. Sorry, I have been using the construction for over 20 years so I forget that it might not be clear to others. | |
| Apr 24, 2021 at 14:12 | comment | added | Benjamin Steinberg | That's right, you are only allowed to follow edges in the correct direction. Otherwise you wouldn't be able to us this algorithm to check membership in submonoids and also if you could read the g edge backward you would get into trouble | |
| Apr 24, 2021 at 14:07 | comment | added | Ashot Minasyan | So, in your automaton you can only consider directed paths? For Stallings graphs, one can move against the direction of an edge, by reading the inverse of its label... Also, do you assume that $g \neq 1$, to ensure that the start and the accept vertices in the automaton for $HgK$ are distinct? I've realised that the method I suggest above will generate the core graph for $\langle H,gKg^{-1}\rangle$, so the start and ennd vertices get identified iff $g \in \langle H,gKg^{-1}\rangle$. | |
| Apr 24, 2021 at 13:59 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
deleted 1 character in body
|
| Apr 24, 2021 at 13:58 | comment | added | Benjamin Steinberg | Also I added a slight correction in that you have to have loops for the inverse generators for H and K to get the subgroup instead of submonoid. | |
| Apr 24, 2021 at 13:55 | comment | added | Benjamin Steinberg | The problem is if you do HgK and g is in H or K you will fold things into the subgroup graph for <H,K>. Folding only works really for things like subgroups where there is no left to right direction. | |
| Apr 24, 2021 at 13:53 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 63 characters in body
|
| Apr 24, 2021 at 13:45 | comment | added | Ashot Minasyan | Thank you for such a useful answer! It seems to me that the main difference from Stallings foldings is that we add $\epsilon$-edges instead of folding. I wonder if Stallings' method can be made to work here as well? To decide if $g \in HK$, build the automaton for $HgK$, as you suggest, marking the start vertex and the end vertex by different colours. Apply Stallings foldings to the resulting graph. Then $g \in HK$ iff the start and end vertices have been identified after the foldings are done. | |
| Apr 24, 2021 at 13:28 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 27 characters in body
|
| Apr 24, 2021 at 13:18 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 202 characters in body
|
| Apr 24, 2021 at 13:13 | history | answered | Benjamin Steinberg | CC BY-SA 4.0 |