In message <[EMAIL PROTECTED]>,
Ian Phillipps writes:
: 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?
CSL is Context-Sensitive Language, i.e., a language that can be
generated by a context-sensitive grammar. See
<URL:http://www.wikipedia.com/wiki/Context-sensitive_grammar>
According to that page, the "decision problem that asks wether a certain
string s belongs to the language of a certain context-sensitive grammar
G, is undecidable. Similarly, the decision problem that asks whether a
certain context-sensitive grammar G defines a nonempty language is also
undecidable." That news isn't as bad as it sounds, though; it suggests
that CSGs might not be the best tool for parsing CSLs. (A fellow named
Maurice Gittens wrote a yacc-alike tool for parsing with augmented CSGs:
<URL:http://www.gits.nl/grammar.html>.)
PSPACE is a complexity class, i.e., decision problems that can be
solved using a polynomial (in the size of the input) amount of space
on a deterministic Turing machine. P and NP might be better named as
PTIME and NPTIME.
Greg, who thinks formal languages and complexity theory are fun
