On Thu, Oct 25, 2001 at 02:24:33PM +0100, Ian Phillipps wrote:
> Should have been a smiley.
Well it made me smile :-)
> OTOHUAAAPITA.
"on the other hand undefined acronyms are a pain in the arse"?
> > [ PSPACE-complete ]
> Is it related to NP-complete?
Yes, very much so. But even worse :-)
PSPACE is the class of problems which can be solved using only a
polynomial amount of memory. It includes all of NP, and quite possibly
more as well. Nobody knows for sure.
In practice that means that PSPACE-complete problems can't even be
shown to be in NP at all, and probably aren't. So PSPACE-completeness
is worse than NP-completeness.
>> [CFG for prime-length strings]
> .... but you can do that sort of thing with Perl's 'R'E, too:
True. I think that Perl's 'R'Es are even more powerful than "pure"
regular-expressions-with-backreferences, because of the lookahead
operators[2].
/^(?!(xx+)\1+$)(?=xx+$)/
will literally match only prime-length strings of x's, and I don't
think you can do that with pure rewbrs[1].
(There are a lot of fascinating unexplored theoretical questions
here which I'm starting to investigate. If anyone happens to be
interested in the details, mail me off-list.)
.robin.
[1] "rewbr" is Aho's abbreviation for "regular exprssion with back
referencing". I think I prefer the French translation "erara" :-)
[2] formally speaking, they mean that (Perl regex)-expressible
languages are closed under intersection and relative complement.
I don't think that rewbr-expressible languages are closed under
relative complement -- not yet sure about intersection.
