Monadic second-order definable graph transductions: a survey

DOI10.1016/0304-3975(94)90268-2MaRDI QIDQ1325847zbMATH OpenOpenAlexFDO

Authors 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

context-free languagesdefinable transductionsgraph transductionshyperedge replacementmonadic second-order logicParikh's theoremvertex replacement

Mathematics Subject Classification ID

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

Recommendations

• The monadic second-order logic of graphs. VII: Graphs as relational structures
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cites work

• A comparison of boundary graph grammars and context-free hypergraph grammars
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• Decision Problems of Finite Automata Design and Related Arithmetics
• Easy problems for tree-decomposable graphs
• Graph expressions and graph rewritings
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 3846895 (Why is no real title available?)
• scientific article; zbMATH DE number 3825213 (Why is no real title available?)
• scientific article; zbMATH DE number 4049099 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 17539 (Why is no real title available?)
• scientific article; zbMATH DE number 177419 (Why is no real title available?)
• scientific article; zbMATH DE number 177441 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 475423 (Why is no real title available?)
• scientific article; zbMATH DE number 475615 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• scientific article; zbMATH DE number 3304995 (Why is no real title available?)
• Hyperedge replacement: grammars and languages
• Hypergraph languages of bounded degree
• Monadic second-order evaluations on tree-decomposable graphs
• Structural properties of context-free sets of graphs generated by vertex replacement
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• 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
• The string generating power of context-free hypergraph grammars
• Tree acceptors and some of their applications
• Tree transducers, L systems, and two-way machines
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(80)

• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• A regular characterization of graph languages definable in monadic second-order logic
• Nondeterministic operations on finite relational structures
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• Monadic second-order definable text languages
• The monadic second-order logic of graphs. X: Linear orderings
• Logical description of context-free graph languages
• A monadic second-order definition of the structure of convex hypergraphs.
• Query efficient implementation of graphs of bounded clique-width
• 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
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• The evaluation of first-order substitution is monadic second-order compatible
• Monadic second-order logic on tree-like structures
• Finite graph automata for linear and boundary graph languages
• The monadic second-order logic of graphs. VIII: Orientations
• On infinite transition graphs having a decidable monadic theory
• 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.
• Towards a language theory for infinite N-free pomsets.
• Regular sets of infinite message sequence charts
• The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs
• Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
• Regular model checking with regular relations
• Streamable regular transductions
• Clique-width and edge contraction
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• Recognizability, hypergraph operations, and logical types
• Deciding regular grammar logics with converse through first-order logic
• The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic
• Satisfiability of \(\operatorname{ECTL}^\ast\) with constraints
• A survey on decidable equivalence problems for tree transducers
• Regular Programming for Quantitative Properties of Data Streams
• Regular Transformations of Data Words Through Origin Information
• Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
• Minimalist grammars in the light of logic
• Weighted Logics for Nested Words and Algebraic Formal Power Series
• On the monadic second-order transduction hierarchy
• scientific article; zbMATH DE number 17791 (Why is no real title available?)
• scientific article; zbMATH DE number 4124985 (Why is no real title available?)
• Verification of graph grammars using a logical approach
• On the structure of linear apex NLC graph grammars
• The definition in monadic second-order logic of modular decompositions of ordered graphs
• scientific article; zbMATH DE number 2087418 (Why is no real title available?)
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• Graph operations, graph transformations and monadic second-order logic: a survey
• scientific article; zbMATH DE number 1456961 (Why is no real title available?)
• A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic.
• scientific article; zbMATH DE number 7559409 (Why is no real title available?)
• scientific article; zbMATH DE number 7559449 (Why is no real title available?)
• On canonical models for rational functions over infinite words
• scientific article; zbMATH DE number 7561353 (Why is no real title available?)
• Formal verification of graph grammars using mathematical induction
• Graph Transformations
• Relational structures constructible by quantifier free definable operations
• Synthesis of data word transducers
• From two-way transducers to regular function expressions
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Algorithmic uses of the Feferman-Vaught theorem
• Transduction from trees to graphs through folding
• Efficient construction of reversible transducers from regular transducer expressions
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• Preservation theorems through the Lens of topology
• Decidable (ac)counting with Parikh and Muller: adding Presburger arithmetic to monadic second-order logic over tree-interpretable structures
• Reversible transducers over infinite words
• Shape preserving tree transducers
• The structure of trees in the pushdown hierarchy
• A logical characterization of weak determinism as simultaneous application
• Expressiveness results for an inductive logic of separated relations
• Decidability of querying first-order theories via countermodels of finite width
• Twin-width. IV: Ordered graphs and matrices
• Labelled well quasi ordered classes of bounded linear clique-width
• Reversible pebble transducers
• Trees, grids, and MSO decidability: from graphs to matroids
• Existential MSO over two successors is strictly weaker than over linear orders
• Definable transductions and weighted logics for texts
• The equivalence problem for deterministic MSO tree transducers is decidable
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Circle graphs and monadic second-order logic

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

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