Suppose I give you two arbitrary regular expressions. Are they equivalent?

Does there exist an algorithm to determine whether two regexes are 
equivalent? What complexity class does this algorithm live in? What does 
"equivalent" even mean in this context? What about if one expression 
matches a subset of the other? Or a superset? Or in general two 
partially-overlapping sets?

Post a reply to this message

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.

> Does there exist an algorithm to determine whether two regexes are
> equivalent? What complexity class does this algorithm live in? What does
> "equivalent" even mean in this context? What about if one expression
> matches a subset of the other? Or a superset? Or in general two
> partially-overlapping sets?

There exists a Perl library to do some related computations of this 
sort, although it will sometimes fail to detect an equivalence (but I 
think never detects a false equivalence).

http://search.cpan.org/~vbar/Regexp-Compare-0.17/lib/Regexp/Compare.pm

Post a reply to this message

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

On 5/24/2013 12:22 PM, Warp wrote:
> 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.

I should have been more explicit: solved by converting each regex into a 
*minimal* DFA  and checking if they are isomorphic.

Graph isomorphism is of course GI-complete, but the conversion to a 
minimal DFA is in general PSPACE-complete.

Post a reply to this message

On 24/05/2013 07:44 PM, Kevin Wampler 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.

Does the situation change if we disallow the Kleene star?

Post a reply to this message

On 2013-05-24 13:20, Orchid Win7 v1 wrote:
> Suppose I give you two arbitrary regular expressions. Are they equivalent?
>
> Does there exist an algorithm to determine whether two regexes are
> equivalent?

Piece of cake:

if( string RegExp1 == string RegExp2 ){
	printf( "They're equivalent!\n" );
}else{
	printf( "They're not identically equivalent!\n" );
}

*wink*

Post a reply to this message

>> Does there exist an algorithm to determine whether two regexes are
>> equivalent?
>
> Piece of cake:
>
> if( string RegExp1 == string RegExp2 ){
> printf( "They're equivalent!\n" );
> }else{
> printf( "They're not identically equivalent!\n" );
> }
>
> *wink*

Oh come on. You could at least parse the string into an AST and compare 
the two ASTs. :-P That would at least remove trivial differences like 
extra spaces and so on.

Post a reply to this message

On 5/25/2013 1:30 AM, Orchid Win7 v1 wrote:
>
> Does the situation change if we disallow the Kleene star?

Yes, although not usefully so.  Without the Kleene star it's co-NP complete.

Post a reply to this message