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

DOI10.1016/S0304-3975(99)00258-3zbMath0930.68073MaRDI QIDQ1960412

Changwook Kim, Tae Eui Jeong

Publication date: 12 January 2000

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

zbMATH Keywords

complexity; normal forms; formal languages; graph grammars

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Separation results for separated apex NLC and NCE graph languages, Double Greibach operator grammars

Cites Work

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