Complexity of boundary graph languages

DOI10.1051/ITA/1990240302671MaRDI QIDQ3479528zbMATH OpenOpenAlexFDO

Authors George Leih, Joost Engelfriet

Publication date 1990

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92359

zbMATH Keywords

graph grammarsgraph languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Grammars and rewriting systems (68Q42)

Cites work

• scientific article; zbMATH DE number 3943061 (Why is no real title available?)
• scientific article; zbMATH DE number 4049102 (Why is no real title available?)
• scientific article; zbMATH DE number 4049105 (Why is no real title available?)
• scientific article; zbMATH DE number 4060748 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (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
• Graph grammars with neighbourhood-controlled embedding
• Linear graph grammars: Power and complexity
• On sequential and parallel node-rewriting graph grammars
• On the Tape Complexity of Deterministic Context-Free Languages
• On the structure of node-label-controlled graph languages
• The complexity of regular DNLC graph languages
• Tree-size bounded alternation

Cited in

(16)

• HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
• HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting
• On the structure of linear apex NLC graph grammars
• Nonterminal separation in graph grammars
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Boundary graph grammars with dynamic edge relabeling
• Efficient recognition algorithms for boundary and linear eNCE graph languages
• Separation results for separated apex NLC and NCE graph languages
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• Separating \(k\)-separated eNCE graph languages
• A hierarchy of eNCE families of graph languages
• Non-perturbative graph languages, halting problem and complexity
• The complexity of regular DNLC graph languages
• Bound graph polysemy
• Finite graph automata for linear and boundary graph languages
• The bounded degree problem for eNCE graph grammars

This page was built for publication: Complexity of boundary graph languages

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