Complexity of boundary graph languages
From MaRDI portal
Publication:3479528
DOI10.1051/ita/1990240302671zbMath0701.68062OpenAlexW22407023MaRDI QIDQ3479528
Publication date: 1990
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92359
Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (12)
The equivalence of boundary and confluent graph grammars on graph languages of bounded degree ⋮ The bounded degree problem for eNCE graph grammars ⋮ A hierarchy of eNCE families of graph languages ⋮ The complexity of regular DNLC graph languages ⋮ On the structure of linear apex NLC graph grammars ⋮ A comparison of boundary graph grammars and context-free hypergraph grammars ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting ⋮ Finite graph automata for linear and boundary graph languages ⋮ Separation results for separated apex NLC and NCE graph languages ⋮ Nonterminal separation in graph grammars ⋮ Separating \(k\)-separated eNCE graph languages
Cites Work
- The complexity of regular DNLC graph languages
- Boundary graph grammars with dynamic edge relabeling
- A comparison of boundary graph grammars and context-free hypergraph grammars
- Tree-size bounded alternation
- On the structure of node-label-controlled graph languages
- Graph grammars with neighbourhood-controlled embedding
- Linear graph grammars: Power and complexity
- On sequential and parallel node-rewriting graph grammars
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- On the Tape Complexity of Deterministic Context-Free Languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity of boundary graph languages
