scientific article

zbMath0649.68075MaRDI QIDQ3795250

Clemens Lautemann

Publication date: 1988

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

complexitygraph grammarhyperedge replacement grammarscontext-free graph languagesboundary node-label controlled grammarscontext-free string languages

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)

Related Items (18)

Handle-rewriting hypergraph grammars ⋮ 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 ⋮ The monadic second-order logic of graphs. I: Recognizable sets of finite graphs ⋮ Complexity of boundary graph languages ⋮ The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues ⋮ Power properties of NLC graph grammars with a polynomial membership problem ⋮ The monadic second-order logic of graphs : Definable sets of finite graphs ⋮ The complexity of regular DNLC graph languages ⋮ A comparison of boundary graph grammars and context-free hypergraph grammars ⋮ The string generating power of context-free hypergraph grammars ⋮ Complexity of path-forming games ⋮ The complexity of graph languages generated by hyperedge replacement ⋮ A Greibach normal form for context-free graph grammars ⋮ Two strikes against perfect phylogeny ⋮ Generating irregular partitionable data structures ⋮ On hyperedge replacement and BNLC graph grammars ⋮ Hypergraph languages of bounded degree

This page was built for publication: