Subject: Re: Sugar - Complexity Question
From: Moshe Vardi (vardi@cs.rice.edu)
Date: Mon Jul 09 2001 - 07:50:48 PDT
>
> >It is known that universality of SERE is EXPSPACE-complete, so I doubt
> >that you'll be able to beat that lower bound.
>
> ok. thanks for the complexity lesson. can you give us a reference to this
> result?
Martin Fuerer: The Complexity of the Inequivalence Problem for Regular
Expressions with Intersection. ICALP 1980: 234-245
>
> we have been trying to understand our implementation in light of this
> information. it seems that ~ (overlapping concatention) which is the \
> operator (glue) in forspec, causes exponential blow-up as well, thus giving
> a double exponent after determinization. do you agree that overlapping
> concatenation/glue causes a double exponential blow-up?
No, I don't see why this would cuase a blow-up. ForSpec has glue and it
still has only a single-exponential time complexity (PSPACE).
I am still puzzled by the footnote about "rewriting away intersection
and glue", which appears in your CAV'01 paper. Does your implementation
support the full language?
Thanks,
Moshe
This archive was generated by hypermail 2b28 : Mon Jul 09 2001 - 07:51:28 PDT