Combinatorial properties of boundary NLC graph languages

DOI10.1016/0166-218X(87)90054-0MaRDI QIDQ1089808zbMATH OpenOpenAlexWikidataFDO

Authors Grzegorz Rozenberg, Emo Welzl

Publication date 1987

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(87)90054-0

zbMATH Keywords

chromatic numberclique numbergraph grammarsindex of a graphnode label controlled grammarsadjacency structurebehaviour of graph invariantsBNLC languagesnode labeled undirected graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Structural characterization of families of graphs (05C75)

Recommendations

• Graph theoretic closure properties of the family of boundary NLC graph languages
• scientific article; zbMATH DE number 3890755
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• The generating power of boundary NLC graph grammars and cycle graphs
• scientific article; zbMATH DE number 3943059

Cites work

• scientific article; zbMATH DE number 3644498 (Why is no real title available?)
• scientific article; zbMATH DE number 3885330 (Why is no real title available?)
• scientific article; zbMATH DE number 3852433 (Why is no real title available?)
• scientific article; zbMATH DE number 3633737 (Why is no real title available?)
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Decision problems for node label controlled graph grammars
• Graph theoretic closure properties of the family of boundary NLC graph languages
• Graph theory
• On the structure of node-label-controlled graph languages
• Parallel concepts in graph theory
• Restrictions on NLC graph grammars
• Restrictions, extensions, and variations of NLC grammars
• Sur le coloriage des graphs

Cited in

(19)

• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• The complexity of connectivity problems on context-free graph languages
• A pumping lemma and the structure of derivations in the boundary NLC graph languages
• A comparison of boundary graph grammars and context-free hypergraph grammars
• A hierarchy of the class of apex NLC graph languages by bounds on the number of nonterminal nodes in productions
• The generating power of boundary NLC graph grammars and cycle graphs
• Separating \(k\)-separated eNCE graph languages
• Graph theoretic closure properties of the family of boundary NLC graph languages
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• Linear graph grammars: Power and complexity
• scientific article; zbMATH DE number 3890755 (Why is no real title available?)
• A normal form problem for unlabeled boundary NLC graph languages
• Algorithms for graph problems on BNLC structured garphs
• Boundary graph grammars with dynamic edge relabeling
• Logical description of context-free graph languages
• HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
• On hyperedge replacement and BNLC graph grammars
• Nonterminal separation in graph grammars
• scientific article; zbMATH DE number 3943059 (Why is no real title available?)

This page was built for publication: Combinatorial properties of boundary NLC graph languages

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