The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
From MaRDI portal
Publication:1854438
DOI10.1006/inco.2000.3021zbMath1005.68089OpenAlexW2052140716MaRDI QIDQ1854438
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.2000.3021
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The bounded degree problem for NLC grammars is decidable
- Hyperedge replacement: grammars and languages
- Boundary graph grammars with dynamic edge relabeling
- A comparison of boundary graph grammars and context-free hypergraph grammars
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- On the structure of node-label-controlled graph languages
- Restrictions, extensions, and variations of NLC grammars
- Formal languages of labelled graphs
- A partial k-arboretum of graphs with bounded treewidth
- The bounded degree problem for eNCE graph grammars
- Linear graph grammars: Power and complexity
- Structural properties of context-free sets of graphs generated by vertex replacement
- Emptiness problems of eNCE graph languages
- Handle-rewriting hypergraph grammars
- Easy problems for tree-decomposable graphs
- Languages that Capture Complexity Classes
- Graph expressions and graph rewritings
- Handbook of Graph Grammars and Computing by Graph Transformation
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
