scientific article; zbMATH DE number 4060748

MaRDI QIDQ3795250zbMATH OpenFDO

Authors Clemens Lautemann

Publication date 1988

zbMATH Keywords

boundary node-label controlled grammarscomplexitycontext-free graph languagescontext-free string languagesgraph grammarhyperedge replacement grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3885330
• Efficient decision procedures for graph properties on context-free graph languages
• The complexity of graph languages generated by hyperedge replacement
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• scientific article; zbMATH DE number 3872712

Cited in

(39)

• Testing for grammatical coverings
• Power properties of NLC graph grammars with a polynomial membership problem
• Algorithms for graph problems on BNLC structured garphs
• The string generating power of context-free hypergraph grammars
• On multiple context-free grammars
• Upper bounds on recognition of a hierarchy of non-context-free languages
• Complexity of path-forming games
• On hyperedge replacement and BNLC graph grammars
• Hypergraph languages of bounded degree
• The complexity of connectivity problems on context-free graph languages
• Improved self-reduction algorithms for graphs with bounded treewidth
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Context-free graph grammars and concatenation of graphs
• Generating irregular partitionable data structures
• Set of memories of a D-graph
• Powerful and NP-complete: hypergraph Lambek grammars
• The complexity of graph languages generated by hyperedge replacement
• Handle-rewriting hypergraph grammars
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• scientific article; zbMATH DE number 3885330 (Why is no real title available?)
• Complexity of boundary graph languages
• scientific article; zbMATH DE number 3909759 (Why is no real title available?)
• scientific article; zbMATH DE number 4060749 (Why is no real title available?)
• scientific article; zbMATH DE number 17563 (Why is no real title available?)
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• scientific article; zbMATH DE number 177455 (Why is no real title available?)
• scientific article; zbMATH DE number 1107740 (Why is no real title available?)
• scientific article; zbMATH DE number 1504824 (Why is no real title available?)
• scientific article; zbMATH DE number 3999291 (Why is no real title available?)
• A Greibach normal form for context-free graph grammars
• Two strikes against perfect phylogeny
• Efficient decision procedures for graph properties on context-free graph languages
• scientific article; zbMATH DE number 4189193 (Why is no real title available?)
• Parallel algorithms for a class of graphs generated recursively
• Efficient recognition algorithms for boundary and linear eNCE graph languages
• The monadic second-order logic of graphs : Definable sets of finite graphs
• Recognising k-connected hypergraphs in cubic time
• The complexity of regular DNLC graph languages
• A comparison of boundary graph grammars and context-free hypergraph grammars

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3795250)