HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting

DOI10.1016/S0304-3975(99)00258-3zbMATH Open0930.68073OpenAlexW1966166590MaRDI QIDQ1960412FDOQ1960412

Changwook Kim, Tae Eui Jeong

Publication date: 12 January 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00258-3

zbMATH Keywords

complexitynormal formsformal languagesgraph grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Handle-rewriting hypergraph grammars
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• On the structure of node-label-controlled graph languages
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Apex graph grammars and attribute grammars
• Graph grammars with neighbourhood-controlled embedding
• Separating \(k\)-separated eNCE graph languages
• A hierarchy of eNCE families of graph languages
• Linear graph grammars: Power and complexity
• Node replacement graph languages squeezed with chains, trees, and forests
• Neighborhood-uniform NLC grammars
• Complexity of boundary graph languages
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Nonterminal separation in graph grammars
• Boundary graph grammars with dynamic edge relabeling
• On the Tape Complexity of Deterministic Context-Free Languages
• Edge-label controlled graph grammars
• Restrictions, extensions, and variations of NLC grammars
• Decision problems for node label controlled graph grammars
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Graph expressions and graph rewritings
• The complexity of graph languages generated by hyperedge replacement
• Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
• Graph-grammars and their application to computer science. 2nd International Workshop, Haus Ohrbeck, Germany, October 4-8, 1982. Under the auspices of the European Association for Theoretical Computer Science
• Graph-grammars and their application to computer science and biology. International workshop Bad Honnef, October 30 November 3, 1978
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• Graph theoretic closure properties of the family of boundary NLC graph languages
• Combinatorial properties of boundary NLC graph languages
• The NP-completeness column: An ongoing guide
• Graph grammars and their application to computer science. 5th international workshop, Williamsburg, VA, USA, November 13--18, 1994. Selected papers
• Handle NLC grammars and r. e. languages
• The complexity of regular DNLC graph languages
• Metatheorems for decision problems on hyperedge replacement graph languages
• Hypergraph languages of bounded degree

Cited In (5)

• Title not available (Why is that?)
• Node replacement graph grammars with dynamic node relabeling
• Separation results for separated apex NLC and NCE graph languages
• Node replacement in hypergraphs: Simulation of hyperedge replacement, and decidability of confluence
• Double Greibach operator grammars

Recommendations

• Hyperedge replacement: grammars and languages 👍 👎
• Linear graph grammars: Power and complexity 👍 👎
• The generative power of context-free node rewriting in hypergraphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting

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