Separation results for separated apex NLC and NCE graph languages

DOI10.1006/JCSS.2001.1749MaRDI QIDQ5946057zbMATH OpenOpenAlexFDO

Authors Changwook Kim

Publication date 14 October 2001

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.2001.1749

zbMATH Keywords

node replacement graph languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Separating \(k\)-separated eNCE graph languages
• A hierarchy of the class of apex NLC graph languages by bounds on the number of nonterminal nodes in productions
• Nonterminal bounded NLC graph grammars
• Nonterminal separation in graph grammars
• A hierarchy of eNCE families of graph languages

Cites work

• A comparison of boundary graph grammars and context-free hypergraph grammars
• A hierarchy of eNCE families of graph languages
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Apex graph grammars and attribute grammars
• Boundary graph grammars with dynamic edge relabeling
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Complexity of boundary graph languages
• Graph expressions and graph rewritings
• Graph grammars with neighbourhood-controlled embedding
• Handbook of Graph Grammars and Computing by Graph Transformation
• Handle-rewriting hypergraph grammars
• HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
• scientific article; zbMATH DE number 4035178 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Linear graph grammars: Power and complexity
• Metatheorems for decision problems on hyperedge replacement graph languages
• Node replacement graph languages squeezed with chains, trees, and forests
• Nonterminal bounded NLC graph grammars
• Nonterminal separation in graph grammars
• On sequential and parallel node-rewriting graph grammars
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• Separating \(k\)-separated eNCE graph languages
• The complexity of regular DNLC graph languages

Cited in

(6)

• A hierarchy of eNCE families of graph languages
• Node replacement graph languages squeezed with chains, trees, and forests
• A hierarchy of the class of apex NLC graph languages by bounds on the number of nonterminal nodes in productions
• Node replacement graph grammars with dynamic node relabeling
• On the structure of linear apex NLC graph grammars
• Nonterminal separation in graph grammars

This page was built for publication: Separation results for separated apex NLC and NCE graph languages

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