The bounded degree problem for eNCE graph grammars

DOI10.1006/INCO.1997.2628MaRDI QIDQ1363781zbMATH OpenOpenAlexFDO

Authors Konstantin Skodinis, Egon Wanke

Publication date 11 August 1997

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1997.2628

zbMATH Keywords

graph grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• The bounded degree problem for non-obstructing eNCE graph grammars
• Emptiness problems of eNCE graph languages
• The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
• scientific article; zbMATH DE number 1107740

Cites work

• scientific article; zbMATH DE number 4049100 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Boundary graph grammars with dynamic edge relabeling
• Complexity of boundary graph languages
• Emptiness problems of eNCE graph languages
• Handle-rewriting hypergraph grammars
• Hyperedge replacement: grammars and languages
• Languages that Capture Complexity Classes
• Linear graph grammars: Power and complexity
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• Structural properties of context-free sets of graphs generated by vertex replacement
• The bounded degree problem for NLC grammars is decidable
• The complexity of graph languages generated by hyperedge replacement
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree

Cited in

(8)

• Emptiness problems of eNCE graph languages
• The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
• Node replacements in embedding normal form.
• The bounded degree problem for NLC grammars is decidable
• Exponential time analysis of confluent and boundary eNCE graph languages
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• The bounded degree problem for non-obstructing eNCE graph grammars
• Finite graph automata for linear and boundary graph languages

This page was built for publication: The bounded degree problem for eNCE graph grammars

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