Publication:4852905
From MaRDI portal
zbMath0830.68098MaRDI QIDQ4852905
Bruno Courcelle, Joost Engelfriet
Publication date: 30 November 1995
68R10: Graph theory (including graph drawing) in computer science
68Q42: Grammars and rewriting systems
Related Items
On spectra of sentences of monadic second order logic with counting, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Algorithmic uses of the Feferman-Vaught theorem, Trees, grids, and MSO decidability: from graphs to matroids, Vertex-minors, monadic second-order logic, and a conjecture by Seese, The monadic second-order logic of graphs. VII: Graphs as relational structures, Nondeterministic operations on finite relational structures, Hypergraph languages of bounded degree, Monadic second-order definable graph transductions: a survey, The monadic second order logic of graphs. VI: On several representations of graphs by relational structures, Context-free graph languages of bounded degree are generated by apex graph grammars, Logical description of context-free graph languages, A monadic second-order definition of the structure of convex hypergraphs., Tree-width and the monadic quantifier hierarchy., A comparison of tree transductions defined by monadic second order logic and by attribute grammars, Tree-based picture generation, The monadic second-order logic of graphs. VIII: Orientations, Macro tree transducers, attribute grammars, and MSO definable tree translations., The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., Upper bounds to the clique width of graphs, Counting truth assignments of formulas of bounded tree-width or clique-width, The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hyperedge replacement: grammars and languages
- Monadic second-order evaluations on tree-decomposable graphs
- A comparison of boundary graph grammars and context-free hypergraph grammars
- Graph minors. V. Excluding a planar graph
- Characteristics of graph languages generated by edge replacement
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Metatheorems for decision problems on hyperedge replacement graph languages
- The string generating power of context-free hypergraph grammars
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- Hypergraph languages of bounded degree
- Monadic second-order definable graph transductions: a survey
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- Structural properties of context-free sets of graphs generated by vertex replacement
- Graph minors. XIII: The disjoint paths problem
- Handle-rewriting hypergraph grammars
- Tree acceptors and some of their applications
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Weak Second‐Order Arithmetic and Finite Automata
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- Graph expressions and graph rewritings
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Generalized finite automata theory with an application to a decision problem of second-order logic
