On Wed, 24 Oct 2001 at 19:33:25 +0100, Robin Houston wrote:
> On Wed, Oct 24, 2001 at 01:05:38PM -0500, Greg Bacon wrote:
>
> > but my recollection is that determining whether a string is in a CSL
> > is a problem in PSPACE (and maybe PSPACE-complete).
>
> Yes, recognising CSLs is PSPACE-complete in general.
>
> (CSGs are ridiculously powerful, *MUCH* more than Perl regular
> expressions.)
I don't normally like to butt into a private conversation, but could
someone explain to me (I'm only here for the the Fun, you see) what CSL
and PSPACE is?
I did ask Google, which told me that:
"The main result: the satisfiability problem for each of
these explicit modal logics belongs to the class Sigma_2 in
the polynomial hierarchy."
Ah, well.
Oh, the CSL web site looks more fun (www.csl.com).
Ian
