The bounded degree problem for non-obstructing eNCE graph grammars

DOI10.1007/3-540-61228-9_89MaRDI QIDQ4645278zbMATH OpenOpenAlexFDO

Authors Konstantin Skodinis, Egon Wanke

Publication date 10 January 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61228-9_89

zbMATH Keywords

derivation stepedge labelgraph grammarlabeled graphnode label

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• The bounded degree problem for eNCE graph grammars
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• The bounded degree problem for NLC grammars is decidable
• Nonterminal bounded NLC graph grammars
• scientific article; zbMATH DE number 3885330
• scientific article; zbMATH DE number 3872712
• scientific article; zbMATH DE number 1107740
• scientific article; zbMATH DE number 4051027
• scientific article; zbMATH DE number 3852433
• Context-free graph languages of bounded degree are generated by apex graph grammars

Cites work

• Boundary graph grammars with dynamic edge relabeling
• Emptiness problems of eNCE graph languages
• scientific article; zbMATH DE number 3943061 (Why is no real title available?)
• scientific article; zbMATH DE number 4049100 (Why is no real title available?)
• scientific article; zbMATH DE number 4049101 (Why is no real title available?)
• Hyperedge replacement: grammars and languages
• Languages that Capture Complexity Classes
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• The bounded degree problem for NLC grammars is decidable

Cited in

(4)

• The bounded degree problem for eNCE graph grammars
• The obstructions of a minor-closed set of graphs defined by a context-free grammar
• Emptiness problems of eNCE graph languages
• The bounded degree problem for NLC grammars is decidable

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

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