𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graph Operations, Graph Transformations and Monadic Second-Order Logic:: A survey

✍ Scribed by Bruno Courcelle

Book ID
108498239
Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
171 KB
Volume
51
Category
Article
ISSN
1571-0661

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Circle graphs and monadic second-order l
Circle graphs and monadic second-order logic
✍ Bruno Courcelle πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 357 KB

This article is part of a project consisting in expressing, whenever possible, graph properties and graph transformations in monadic second-order logic or in its extensions using modulo p cardinality set predicates or auxiliary linear orders. A circle graph is the intersection graph of a set of chor

The monadic second-order logic of graphs
The monadic second-order logic of graphs XIV: uniformly sparse graphs and edge set quantifications
✍ Bruno Courcelle πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 342 KB

We consider the class US k of uniformly k-sparse simple graphs, i.e., the class of ΓΏnite or countable simple graphs, every ΓΏnite subgraph of which has a number of edges bounded by k times the number of vertices. We prove that for each k, every monadic second-order formula (intended to express a grap

A Comparison of Tree Transductions Defin
A Comparison of Tree Transductions Defined by Monadic Second Order Logic and by Attribute Grammars
✍ Roderick Bloem; Joost Engelfriet πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 547 KB

Two well-known formalisms for the specification and computation of tree transductions are compared: the mso graph transducer and the attributed tree transducer with look-ahead, respectively. The mso graph transducer, restricted to trees, uses monadic second order logic to define the output tree in t