Timeline for Group theory with grep?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2023 at 2:38 | answer | added | Wahome | timeline score: 5 | |
| Apr 14, 2022 at 13:15 | answer | added | Lee Mosher | timeline score: 21 | |
| Apr 14, 2022 at 6:56 | comment | added | Sam Nead | @LeeMosher - that really sounds like an answer to the question, and not just a comment… hint, hint. :) | |
| Apr 13, 2022 at 20:54 | comment | added | Derek Holt | @Lee Mosher yes the programs output all of these automata to files. A long time ago I did experiment with programs to find equivalent regular expressions for finite state automata, but they typically came up with horrifically long and unreadable results, even for apparently simple examples like the free gorup of rank 2. In fact it is a nice exercise to produce a shortish regular expression for the set of reduced words. | |
| Apr 13, 2022 at 20:24 | comment | added | Lee Mosher | Of course, this is bass-ackwards, because the regular expression can be much more complicated than the automaton; my understanding is that most of what grep does is to immediately convert the regular expression into an automaton. I'm confident that all Bill needed was a few simple examples to spur him on to the recognition of regular languages and FDAs as useful tools in group theory, and ultimately as the basis of a new theory. | |
| Apr 13, 2022 at 20:23 | comment | added | Lee Mosher | I am the author of that quote. I vaguely remember during that time looking over Bill's shoulder at his computer screen while he did some of those calculations. Be that as it may, here's a followup question for @DerekHolt: Does your software allow the user to, in some sense, output the word recognition automaton and the multiplier automata for an automatic structure on a group? If so, there are other algorithms which could convert those automata into regular expressions, allowing one to use grep. | |
| Apr 13, 2022 at 17:41 | comment | added | Derek Holt | except in some well understood example, like surface groups, and groups satisfying strong small cancellation properties, the Dehn algorithm is more difficult to implement, because it requires knowing the constant $\delta$ of hyperbolicity, and also all relations of total length up to $4\delta$ (or it might be $8\delta$). | |
| Apr 13, 2022 at 17:39 | comment | added | Derek Holt | @Carl-FredrikNybergBrodda Yes I've seen the question, and I heard about Thurston's use of grep very early in the development of the theory. But I think he only used grep in an attempt to recognize words in normal form in some typical examples. Solving the word problem involves reducing the word to normal form letter by letter, and I don't believe that can be done with grep alone. Note also that solving the word problem in automatic groups using this method is quadratic time, whereas in theory it can be solved in linear time in hyperbolic groups using the Dehn algorithm, but ... | |
| Apr 13, 2022 at 17:29 | comment | added | Carl-Fredrik Nyberg Brodda |
@MattF. I'm not sure what you mean by "go inside a loop", so perhaps I'm missing some subtlety. I probably couldn't do it explicitly, as I'm not savvy with automatic groups or grep, but here's a sample pseudo-code; the rest is just finding the multiplying automata (which can be done by "hand"): we want to check if $w \in A^\ast$ is accepted by an automaton $H$. Write down the regex $r$ for $H$. Then put $w$ in a text-file, called w.txt. Then run grep r w.txt. Then $H$ accepts $w$ iff the output is non-empty.
|
|
| Apr 13, 2022 at 17:21 | comment | added | user44143 | @Carl-FredrikNybergBrodda, can you give an example of a group and an “implementation in grep”? I think grep usually needs to go inside a loop, in general a loop whose bounds can’t be computed recursively, and that doesn’t sound like what Thurston was describing. | |
| Apr 13, 2022 at 17:10 | comment | added | Carl-Fredrik Nyberg Brodda |
[contd.] So the fact that many infinite groups, in which the word problem can be quite non-trivial to solve at first glance (e.g. hyperbolic groups, Braid groups), turn out to be automatic, and can hence be computed with using only some fixed set of regular expressions (in grep, or wherever) is the remarkable fact to me. A specific implementation in grep is then more or less trivial to write out, given the finite state automata. There are many explicit such automata in Word Processing. I'm sure Derek Holt will have a lot more nuance to add to this -- let's hope he sees this question.
|
|
| Apr 13, 2022 at 17:10 | comment | added | Carl-Fredrik Nyberg Brodda |
The remarkable thing here is not so much that grep can be used to compute regular expresssions; but that regular expressions (which are equivalent in computing power to finite automata) can be used to compute in groups! An automatic group is in essence a group which (1) has a regular set of representatives for its elements; and (2) a finite automaton for each letter $a$ in the generating set, which simulates what "right multiplying by $a$" does to each representative. Some finite number of automata -- and you can completely describe the word problem of the group! [cont...]
|
|
| Apr 13, 2022 at 16:42 | comment | added | user44143 | grep can test whether a word is in canonical form for some groups, eg the free group on $a,b$ modulo $a^3=b^4=1$, $ba=ab^2$ — but I hope that Thurston saw something more impressive. | |
| S Apr 13, 2022 at 15:37 | review | First questions | |||
| Apr 13, 2022 at 15:46 | |||||
| S Apr 13, 2022 at 15:37 | history | asked | asama | CC BY-SA 4.0 |