scientific article; zbMATH DE number 4051027

MaRDI QIDQ3787507zbMATH OpenFDO

Authors Franz J. Brandenburg

Publication date 1988

zbMATH Keywords

complexity of node rewriting graph grammarsfinite Church-Rosser propertyNLC graph grammarsnode and edge label controlled

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3852433
• scientific article; zbMATH DE number 3885330
• scientific article; zbMATH DE number 3872712
• scientific article; zbMATH DE number 4049100
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity

Cited in

(21)

• Hypergraph languages of bounded degree
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Logical description of context-free graph languages
• Finite graph automata for linear and boundary graph languages
• Linear graph grammars: Power and complexity
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 3852433 (Why is no real title available?)
• REDUCING SIMPLE GRAMMARS: EXPONENTIAL AGAINST HIGHLY-POLYNOMIAL TIME IN PRACTICE
• Graph Transformation in Constant Time
• scientific article; zbMATH DE number 4041319 (Why is no real title available?)
• scientific article; zbMATH DE number 4049095 (Why is no real title available?)
• scientific article; zbMATH DE number 4049100 (Why is no real title available?)
• scientific article; zbMATH DE number 4051037 (Why is no real title available?)
• scientific article; zbMATH DE number 177455 (Why is no real title available?)
• The bounded degree problem for non-obstructing eNCE graph grammars
• Node replacement in hypergraphs: simulation of hyperedge replacement, and decidability of confluence
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• A Greibach normal form for context-free graph grammars
• A polynomial algorithm for the membership problem with categorial grammars
• The power of programmed grammars with graphs from various classes
• The complexity of regular DNLC graph languages

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 Q3787507)