The complexity of graph languages generated by hyperedge replacement
From MaRDI portal
Publication:2277851
DOI10.1007/BF00289017zbMath0725.68055OpenAlexW2088602194MaRDI QIDQ2277851
Publication date: 1990
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00289017
Related Items
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
