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, 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