Complexity of boundary graph languages

DOI10.1051/ITA/1990240302671zbMATH Open0701.68062OpenAlexW22407023MaRDI QIDQ3479528FDOQ3479528

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

• Title not available (Why is that?)
• 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
• Boundary graph grammars with dynamic edge relabeling
• On the Tape Complexity of Deterministic Context-Free Languages
• Tree-size bounded alternation
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of regular DNLC graph languages

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
• Efficient recognition algorithms for boundary and linear eNCE graph languages
• Separation results for separated apex NLC and NCE graph languages
• Nonterminal separation in graph grammars
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Boundary graph grammars with dynamic edge relabeling
• 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)