scientific article; zbMATH DE number 809155
From MaRDI portal
Publication:4852905
zbMath0830.68098MaRDI QIDQ4852905
Joost Engelfriet, Bruno Courcelle
Publication date: 30 November 1995
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)
Related Items (26)
Monadic second-order definable graph transductions: a survey ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions. ⋮ 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 ⋮ Generalized rational relations and their logical definability ⋮ On spectra of sentences of monadic second order logic with counting ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ 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. ⋮ Upper bounds to the clique width of graphs ⋮ The monadic second-order logic of graphs. VII: Graphs as relational structures ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ Unnamed Item ⋮ A Greibach normal form for context-free graph grammars ⋮ Nondeterministic operations on finite relational structures ⋮ 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. ⋮ Hypergraph languages of bounded degree ⋮ Canonisation and Definability for Graphs of Bounded Rank Width
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
This page was built for publication:
