Subject: Re: Sugar - Complexity Question
From: eisner@il.ibm.com
Date: Sun Jul 08 2001 - 07:22:49 PDT
moshe,
>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?
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?
regards,
cindy.
Cindy Eisner
Formal Methods Group Tel: +972-4-8296-266
IBM Haifa Research Laboratory Fax: +972-4-855-0070
Haifa 31905, Israel e-mail:
eisner@il.ibm.com
This archive was generated by hypermail 2b28 : Sun Jul 08 2001 - 07:17:06 PDT