The complexity of connectivity problems on context-free graph languages
From MaRDI portal
Publication:1333400
DOI10.1016/S0022-0000(05)80086-8zbMath0821.68079MaRDI QIDQ1333400
Publication date: 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hyperedge replacement: grammars and languages
- Graph theoretic closure properties of the family of boundary NLC graph languages
- Combinatorial properties of boundary NLC graph 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
- 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
- Algorithms for graph problems on BNLC structured garphs
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- On the decidability of certain integer subgraph problems on context-free graph languages
- Relationships between nondeterministic and deterministic tape complexities
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Graph expressions and graph rewritings
- Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
- Efficient decision procedures for graph properties on context-free graph languages
This page was built for publication: The complexity of connectivity problems on context-free graph languages
