Monadic second-order definable graph transductions: a survey

DOI10.1016/0304-3975(94)90268-2zbMath0805.68077MaRDI 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 logic; context-free languages; Parikh's theorem; hyperedge replacement; definable transductions; graph transductions; vertex replacement

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68R10: Graph theory (including graph drawing) in computer science

68Q42: Grammars and rewriting systems

Related Items

Unnamed Item, Relational structures constructible by quantifier free definable operations, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Algorithmic uses of the Feferman-Vaught theorem, The monadic second-order logic of graphs. IX: Machines and their behaviours, 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, 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, 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, Weighted Logics for Nested Words and Algebraic Formal Power Series

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