Graph theoretic closure properties of the family of boundary NLC graph languages
From MaRDI portal
Publication:1084870
DOI10.1007/BF00289115zbMath0606.68070OpenAlexW2013295728WikidataQ54309858 ScholiaQ54309858MaRDI QIDQ1084870
Grzegorz Rozenberg, Ermo Welzl
Publication date: 1986
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00289115
induced subgraphsgraph grammarconnected graphsBNLC languagediconnected graphsfinite undirected graphs with labelled verticesk-colourable graphsNLC languagenode label controlled grammar
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)
Related Items
A pumping lemma and the structure of derivations in the boundary NLC graph languages, The complexity of connectivity problems on context-free graph languages, The generating power of boundary NLC graph grammars and cycle graphs, Combinatorial properties of boundary NLC graph languages, An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Metatheorems for decision problems on hyperedge replacement graph languages, Decision problems for edge grammars, A hierarchy of eNCE families of graph languages, Graph-theoretic properties compatible with graph derivations, Boundary graph grammars with dynamic edge relabeling, A comparison of boundary graph grammars and context-free hypergraph grammars, HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, Algorithms for graph problems on BNLC structured garphs, Finite graph automata for linear and boundary graph languages, Linear graph grammars: Power and complexity, On hyperedge replacement and BNLC graph grammars, Nonterminal separation in graph grammars, Separating \(k\)-separated eNCE graph languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The bounded degree problem for NLC grammars is decidable
- Restrictions on NLC graph grammars
- On the structure of node-label-controlled graph languages
- Restrictions, extensions, and variations of NLC grammars
- Decision problems for node label controlled graph grammars
- Some simplified NP-complete graph problems
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time