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)
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
68Q42: Grammars and rewriting systems
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
