The complexity of membership for deterministic growing context-sensitive grammars^∗

^∗This research was partially supported by the National Science Foundation under Grant DCR- 8696097 and by the Organized Research Awards Program of the University of Texas at Dallas.

Abstract

In this note, we present an interesting P-complete problem concerning growing context-sensitive grammars, a proper subclass of the context-sensitive grammars. We show that uniform membership for forward deterministic growing context-sensitive grammars is P-complete. As a consequence, we obtain a simple proof for the NP-completeness of the uniform membership problem for growing context- sensitive grammars.

Keywords:

• Complexity
• uniform membership
• growing context-sensitive grammar
• P-complete
• NP-complete

C.R. Categories:

• F.4.2
• F.4.3

^∗This research was partially supported by the National Science Foundation under Grant DCR- 8696097 and by the Organized Research Awards Program of the University of Texas at Dallas.

^∗This research was partially supported by the National Science Foundation under Grant DCR- 8696097 and by the Organized Research Awards Program of the University of Texas at Dallas.

Notes

^∗This research was partially supported by the National Science Foundation under Grant DCR- 8696097 and by the Organized Research Awards Program of the University of Texas at Dallas.