Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
Exponential time analysis of confluent and boundary eNCE graph languages
verfasst von : K. Skodinis, E. Wanke
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
eNCE (edge label neighborhood controlled) graph grammars belong to the most powerful graph rewriting systems with single-node graphs on the left-hand side of the productions. From an algorithmic point of view, confluent and boundary eNCE graph grammars are the most interesting subclasses of eNCE graph grammars. In confluent eNCE graph grammars, the order in which nonterminal nodes are substituted is irrelevant for the resulting graph. In boundary eNCE graph grammars, nonterminal nodes are never adjacent. In this paper, we show that given a confluent or boundary eNCE graph grammar G, the problem whether the language L(G) defined by G is empty, is DEXPTIME-complete.