Complexity metatheorems for context-free grammar problems

摘要

Metatheorems are presented which can be used to (i) establish undecidability results about context-free grammar problems, and (ii) establish lower bounds on certain decidable grammar problems. The main undecidability result is obtained through the simulation of a Turing machine which always halts. This technique promises to be applicable in many situations where conventional techniques for proving undecidability do not succeed.