Graph theoretic closure properties of the family of boundary NLC graph languages

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

zbMATH Keywords

induced subgraphsgraph grammarconnected graphsBNLC languagediconnected graphsfinite undirected graphs with labelled verticesk-colourable graphsNLC languagenode label controlled grammar

Mathematics Subject Classification ID

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