Comment on Given a list of regexes, generate all possible strings that matches all of themComments−groks15yAnyone aware of something which does the exact opposite: given a list of strings generate a regex which matches all, and only those strings? The shorter the regex the better.−audreyt15yUnfortunately, the problem of finding a minimally equivalent regex from an /alt1|alt2|alt3|.../ form is known to be PSPACE-complete ( http://www.computer.org/portal/web/csdl/doi/10.1109/SWAT.197... ), as well as not finitely axiomatizable ( http://www.sciencedirect.com/science/article/pii/S0304397597... ).That means the naïve SMT-solver-based approach in genex will not apply to this problem... Links/suggestions to relevant research welcome! :-)−groks15yWell goddamn. Thanks for the links :-)
Comments
Anyone aware of something which does the exact opposite: given a list of strings generate a regex which matches all, and only those strings? The shorter the regex the better.
Unfortunately, the problem of finding a minimally equivalent regex from an /alt1|alt2|alt3|.../ form is known to be PSPACE-complete ( http://www.computer.org/portal/web/csdl/doi/10.1109/SWAT.197... ), as well as not finitely axiomatizable ( http://www.sciencedirect.com/science/article/pii/S0304397597... ).
That means the naïve SMT-solver-based approach in genex will not apply to this problem... Links/suggestions to relevant research welcome! :-)
Well goddamn. Thanks for the links :-)