Timeline for Is there an algorithm to decide if a word is in a finitely generated subgroup of a free group?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 30, 2018 at 21:44 | comment | added | Benjamin Steinberg | The algorithm is made pretty explicit there. | |
| Dec 30, 2018 at 20:36 | comment | added | Derek Holt | Yes, in general if two cosets are equal, then Todd-Coxeter will eventually establish their equality, but you cannot predict how long it will take (which is inevitable since the question is undecidable). But for free groups, where there are no relations, there is a bound on the total time. | |
| Dec 30, 2018 at 15:11 | comment | added | HJRW | @DerekHolt: Conversely, having "grown up" with Stallings' algorithm, I've never needed to learn the Todd--Coxeter algorithm explicilty, since you can recover it in any group by pulling back to a free group. But I guess Todd--Coxeter comes with no guarantees that it will successfully distinguish cosets in general. | |
| Dec 30, 2018 at 10:51 | comment | added | Derek Holt | In fact the algorithm can be thought of as a special case of Todd-Coxeter coset enumeration. | |
| Dec 30, 2018 at 4:55 | vote | accept | Milo Brandt | ||
| Dec 30, 2018 at 4:32 | history | answered | Andy Putman | CC BY-SA 4.0 |