The complexity of graph languages generated by hyperedge replacement

DOI10.1007/BF00289017zbMath0725.68055OpenAlexW2088602194MaRDI QIDQ2277851

Clemens Lautemann

Publication date: 1990

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00289017

zbMATH Keywords

NP-completegraph grammarsparsinghyperedge replacement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Related Items (18)

Node replacements in embedding normal form. ⋮ The translation power of top-down tree-to-graph transducers ⋮ Probabilistic hyperedge replacement grammars ⋮ The bounded degree problem for eNCE graph grammars ⋮ Uniform parsing for hyperedge replacement grammars ⋮ Predictive Top-Down Parsing for Hyperedge Replacement Grammars ⋮ Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement ⋮ Functional-Logic Graph Parser Combinators ⋮ Unnamed Item ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ An Algorithm for Hypergraph Completion According to Hyperedge Replacement Grammars ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting ⋮ Recognising \(k\)-connected hypergraphs in cubic time ⋮ NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\) ⋮ Second-order abstract categorial grammars as hyperedge replacement grammars ⋮ Generating irregular partitionable data structures ⋮ Rule-based top-down parsing for acyclic contextual hyperedge replacement grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperedge replacement: grammars and languages
• A comparison of boundary graph grammars and context-free hypergraph grammars
• String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Nonterminal bounded NLC graph grammars
• Tree-size bounded alternation
• Towards a complexity theory of synchronous parallel computation
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Properties that characterize LOGCFL
• Graph-grammars and their application to computer science and biology. International workshop Bad Honnef, October 30 November 3, 1978
• 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
• Plex languages
• On Some Variants of the Bandwidth Minimization Problem
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Graph expressions and graph rewritings
• Nondeterministic Space is Closed under Complementation
• Alternation
• Context-free graph grammars
• On the Tape Complexity of Deterministic Context-Free Languages
• Linear and Context-Free Graph Grammars

This page was built for publication: The complexity of graph languages generated by hyperedge replacement