Leftist Grammars Are Non-primitive Recursive

摘要

Leftist grammars were introduced by Motwani et. al. [7], as a tool to show decidability of the accessibility problem in certain general protection systems. It is shown that the membership problem for languages defined by leftist grammars is non-primitive recursive. Therefore, by the reduction of Motwani et. al., the accessibility problem in the appropriate protection systems is non-primitive recursive as well.