Talk:Indexed language

Latest comment: 9 years ago by Jochen Burghardt in topic Example for context-sensitive, but not indexed language

Complexity characterization?

edit

Is there one? Seems like more than PTIME. JMP EAX (talk) 10:32, 17 August 2014 (UTC)Reply

Example for context-sensitive, but not indexed language

edit

Could somebody please provide an example for a language that is context-sensitive, but not indexed? The article says that { (abn)n | n≥0 } isn't indexed; I guess that it is context-sensitive, but I'm unable to establish it (writing context-sensitive grammars is an error-prone task, cf. Talk:Context-sensitive grammar). - Jochen Burghardt (talk) 13:49, 25 February 2015 (UTC)Reply