Kevin Wampler <nob### [at] nowherenet> wrote:
> On 5/24/2013 11:20 AM, Orchid Win7 v1 wrote:
> > Suppose I give you two arbitrary regular expressions. Are they equivalent?

> It depends on what you specifically mean by "regular expression", but 
> probably this problem is PSPACE-complete.  From what I can tell is 
> generally solved by converting each regexp into a DFA and checking if 
> they are isomorphic.

No. Two regular expressions expressing the same "language" (ie. matching
the exact same things) is not a question of isomorphism. Isomorphism is
a much stricter comparison.

For example "a|aa+" and "a+" are equivalent (both match the exact same
things), but not isomorphic (the former has more nodes than the latter.)

The more accurate comparison is the one that says that "every named path
in one graph exists in the other, and vice-versa." I think the term for
this is strong bilinearity. The comparison can be made faster than in
exponential time.

-- 
                                                          - Warp

Post a reply to this message