The Bounded Degree Problem for eNCE Graph Grammars

The complexity of the bounded degree problem is analyzed for graph languages generated by eNCE graph grammars. In particular, the bounded degree problem is shown to be undecidable for eNCE graph grammars, DEXPTIME-complete for confluent/boundary eNCE graph grammars, PSPACE-complete for linear eNCE graph grammars, and P-complete for non-blocking eNCE graph grammars. In our main theorem we show that the bounded degree problem is NL-complete for reduced non-blocking eNCE graph grammars. Many of the shown results carry over to other types of graph grammars.

Authors

• Konstantin Skodinis
• Egon Wanke

Keywords

No keywords are indexed for this paper.