On complexity of grammars related to the safety problem

Leftist grammars were introduced by Motwani et al., who established the relationship between the complexity of the accessibility problem (or safety problem) for certain general protection systems and the membership problem for these grammars. The membership problem for leftist grammars is decidable. This implies the decidability of the accessibility problem. It is shown that the membership problem for leftist grammars is PSPACE-hard. Therefore, the accessibility problem in the appropriate protection systems is PSPACE-hard as well. Furthermore, the PSPACE-hardness result is adapted to a very restricted class of leftist grammars, if the grammar is a part of the input.