Timeline for Algorithm to determine whether two regexes are equivalent
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 20, 2019 at 16:53 | comment | added | D. Ben Knoble | Indeed... must have been my web browser. Odd. Still, it may be preferable to include some of the relevant info so that the answer is self-contained. | |
| Mar 20, 2019 at 16:52 | comment | added | Hendrik Jan | @D.BenKnoble Link works fine for me. | |
| Mar 19, 2019 at 13:27 | comment | added | D. Ben Knoble | Your link is dead. Can you either provide a fresh one or at least some of the relevant info from the paper? | |
| Apr 24, 2015 at 2:38 | comment | added | Ryan Dougherty | Is there a reference for general regular expressions to be PSPACE-complete? | |
| May 28, 2013 at 20:23 | comment | added | Hendrik Jan | @dkuper Thanks for the additional explanation. Feel free to edit the answer to add this or suitable references. (Or even start your own answer.) | |
| May 26, 2013 at 10:11 | comment | added | Denis | it is even EXPSPACE-complete if you allow the square operator (i.e. writing $e^2$ instead of $ee$). It becomes NEXPTIME-complete without the Kleene star. | |
| May 25, 2013 at 20:26 | history | answered | Hendrik Jan | CC BY-SA 3.0 |