Complexity of boundary graph languages

DOI10.1051/ita/1990240302671zbMath0701.68062MaRDI QIDQ3479528

Joost Engelfriet, George Leih

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 grammars; graph languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Separation results for separated apex NLC and NCE graph languages, Nonterminal separation in graph grammars, The complexity of regular DNLC graph languages, A comparison of boundary graph grammars and context-free hypergraph grammars, Separating \(k\)-separated eNCE graph languages, The bounded degree problem for eNCE graph grammars, A hierarchy of eNCE families of graph languages, Finite graph automata for linear and boundary graph languages, HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of regular DNLC graph languages
• Boundary graph grammars with dynamic edge relabeling
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Tree-size bounded alternation
• On the structure of node-label-controlled graph languages
• Graph grammars with neighbourhood-controlled embedding
• Linear graph grammars: Power and complexity
• On sequential and parallel node-rewriting graph grammars
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• On the Tape Complexity of Deterministic Context-Free Languages