Timeline for Easy-to-prove example of non-contextual language
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 30, 2021 at 11:53 | comment | added | Emil Jeřábek | What makes you think this language is not context-sensitive? There are plenty of context-sensitive PSPACE-complete languages, so this fact alone is not helpful. The reason for this is that CSL is not closed under polynomial-time reductions; in fact, the closure of CSL under poly-time reductions is exactly PSPACE. | |
| S Aug 30, 2021 at 9:17 | review | First answers | |||
| Sep 13, 2021 at 9:18 | |||||
| S Aug 30, 2021 at 9:17 | history | answered | Thomas Baruchel | CC BY-SA 4.0 |