Wikipedia: History of Context-sensitive grammar

Difference (from prior major revision) (no other diffs)

Changed: 19,21c19

The decision problem that asks whether a certain string s belongs to the language of a certain context-sensitive grammar G, is PSPACE-complete. Indeed, there are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete.

(Contrary to a previous version of this article, the decision problem is not undecidable.)

The decision problem that asks whether a certain string s belongs to the language of a certain context-sensitive grammar G, is PSPACE-complete (see complexity theory). Indeed, there are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete.

Added: 23a22,24

/Talk?

	Revision 8 . . October 26, 2001 4:00 am by AxelBoldt
	Revision 7 . . October 26, 2001 1:33 am by (logged).92.67.xxx [The decision problem for CSLs is decidable]