8 ms·
Could you give a page number? I skimmed the regular expression section and couldn't find it. Also, while it is self-evident to me that there is a minimal form f
by sirsar 11y ago
Could you give a page number? I skimmed the regular expression section and couldn't find it. Also, while it is self-evident to me that there is a minimal form for each regex, the construction for finding one isn't immediately obvious to me (I can surely enumerate several ways of eliminating redundancy). Beyond that, I'm not sure a minimal form would minimize character length.
Of (a \star b \star ) \star and ( a ∪ b ) \star, which is the canonical form? The transformation from the former to the latter is nontrivial as a \star b \star is not equivalent with a ∪ b.
- areyousure 11y agoOf course, there is a shortest equivalent regular expression, but in general it's PSPACE-complete to find it: https://en.wikipedia.org/wiki/PSPACE-complete#Regular_expressions https://en.wikipedia.org/wiki/PSPACE-complete#Regular_expres... It remains PSPACE-complete if you're given a corresponding DFA: "Jiang and Ravikumar [7] show moreover that the minimization problem for ... regular expressions remains PSPACE-complete, even when specifying the regular language by a dfa" from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.5056&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.... In that sense, the grandparent is incorrect. It is unknown, in both practice and theory, how to find the shortest equivalent regex.
- adrianN 11y agoIt's not unknown, it just takes a long time.
- acchow 11y agoI think you should think deeper on the idea of "unknown"
- adrianN 11y agoI don't understand what you mean. Regex minimization is in PSPACE, so take any PSPACE complete problem, eg Q-Sat, do the reduction and apply the algorithm. Q-Sat can be solved by recursively enumerating all possibilities. So there is a method for minimizing regular expressions. It just takes a long time to run. If you have time you can probably think of an algorithm that works directly on the regex problem without doing the Q-Sat thing. It might even be faster. Heck, there might be an algorithm that works really well in practice. People who do model checking and verification laugh PSPACE completeness in the face and are not even really concerned with undecidability.
- eru 11y agoI would be very interested in finding an approach that works well in practice.
- kragen 11y agoOkay, fine, but in this case N=7. What are the constant factors?