scientific article; zbMATH DE number 4049100

MaRDI QIDQ3785989zbMATH OpenFDO

Authors Franz J. Brandenburg

Publication date 1987

zbMATH Keywords

computational complexityECE embeddingsELC embeddingsNLC embeddingsnode and edge labeled graphsNP-completepartially ordered graph grammarPSPACE-completerewritingspanning treetree-graph grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3872712
• scientific article; zbMATH DE number 3885330
• scientific article; zbMATH DE number 4051027
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Linear graph grammars: Power and complexity

Cited in

(14)

• Power properties of NLC graph grammars with a polynomial membership problem
• The bounded degree problem for eNCE graph grammars
• Generating irregular partitionable data structures
• The complexity of graph languages generated by hyperedge replacement
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 3872712 (Why is no real title available?)
• scientific article; zbMATH DE number 4051027 (Why is no real title available?)
• The bounded degree problem for non-obstructing eNCE graph grammars
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• Exponential time analysis of confluent and boundary eNCE graph languages
• Tree-Based Generation of Restricted Graph Languages
• Nonterminal separation in graph grammars
• Boundary graph grammars with dynamic edge relabeling
• A comparison of boundary graph grammars and context-free hypergraph grammars

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785989)