Monadic second-order definable graph transductions: a survey

DOI10.1016/0304-3975(94)90268-2zbMath0805.68077OpenAlexW1993698725MaRDI QIDQ1325847

Bruno Courcelle

Publication date: 26 January 1995

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90268-2

zbMATH Keywords

monadic second-order logiccontext-free languagesParikh's theoremhyperedge replacementdefinable transductionsgraph transductionsvertex replacement

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)

Related Items (59)

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. ⋮ Towards a language theory for infinite N-free pomsets. ⋮ Satisfiability of \(\operatorname{ECTL}^\ast\) with constraints ⋮ Regular sets of infinite message sequence charts ⋮ Existential MSO over two successors is strictly weaker than over linear orders ⋮ Regular model checking with regular relations ⋮ Definable transductions and weighted logics for texts ⋮ The equivalence problem for deterministic MSO tree transducers is decidable ⋮ Monadic second-order definable text languages ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ The monadic second-order logic of graphs. X: Linear orderings ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Logical description of context-free graph languages ⋮ Unnamed Item ⋮ The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic ⋮ A monadic second-order definition of the structure of convex hypergraphs. ⋮ Transduction from trees to graphs through folding ⋮ Query efficient implementation of graphs of bounded clique-width ⋮ Weighted Logics for Nested Words and Algebraic Formal Power Series ⋮ Verification of graph grammars using a logical approach ⋮ On the structure of linear apex NLC graph grammars ⋮ The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs ⋮ A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic. ⋮ The monadic second-order logic of graphs. IX: Machines and their behaviours ⋮ Circle graphs and monadic second-order logic ⋮ Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory ⋮ The definition in monadic second-order logic of modular decompositions of ordered graphs ⋮ Minimalist Grammars in the Light of Logic ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ The modular decomposition of countable graphs. Definition and construction in monadic second-order logic ⋮ Formal Verification of Graph Grammars using Mathematical Induction ⋮ Finite graph automata for linear and boundary graph languages ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ Recognizability, hypergraph operations, and logical types ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Relational structures constructible by quantifier free definable operations ⋮ Streamable regular transductions ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Regular Programming for Quantitative Properties of Data Streams ⋮ Unnamed Item ⋮ Regular Transformations of Data Words Through Origin Information ⋮ Nondeterministic operations on finite relational structures ⋮ The monadic second-order logic of graphs. XII: Planar graphs and planar maps ⋮ The monadic second-order logic of graphs. XIII: Graph drawings with edge crossings ⋮ Monadic second-order logic, graph coverings and unfoldings of transition systems ⋮ Deciding regular grammar logics with converse through first-order logic ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ The monadic second-order logic of graphs. VIII: Orientations ⋮ From Two-Way Transducers to Regular Function Expressions ⋮ On infinite transition graphs having a decidable monadic theory ⋮ Macro tree transducers, attribute grammars, and MSO definable tree translations. ⋮ The evaluation of first-order substitution is monadic second-order compatible ⋮ Clique-width and edge contraction ⋮ Monadic second-order logic on tree-like structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• A comparison of boundary graph grammars and context-free hypergraph grammars
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Tree transducers, L systems, and two-way machines
• 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
• Structural properties of context-free sets of graphs generated by vertex replacement
• 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
• Easy problems for tree-decomposable graphs
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Graph expressions and graph rewritings
• Decision Problems of Finite Automata Design and Related Arithmetics
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: Monadic second-order definable graph transductions: a survey