Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach (Encyclopedia of Mathematics and its Applications)

Cover
Half Title
Title Page
Copyright
Dedication
Contents
Foreword by Maurice Nivat
Introduction
1 Overview
	1.1 Context-free grammars
	1.2 Inductive sets of properties and recognizability
	1.3 Monadic second-order logic
	1.4 Two graph algebras
	1.5 Fixed-parameter tractability
	1.6 Decidability of monadic second-order logic
	1.7 Graph transductions
	1.8 Monadic second-order logic with edge set quantifications
	1.9 Relational structures
	1.10 References
2 Graph algebras and widths of graphs
	2.1 Algebras and terms
	2.2 Graphs
	2.3 The HR algebra of graphs with sources
	2.4 Tree-decompositions
	2.5 The VR algebra of simple graphs with ports
	2.6 Many-sorted graph algebras
	2.7 References
3 Equational and recognizable sets in many-sorted algebras
	3.1 The equational sets of an algebra
	3.2 Transformations of equation systems
	3.3 Intermezzo on automata
	3.4 The recognizable sets of an algebra
	3.5 References
4 Equational and recognizable sets of graphs
	4.1 HR-equational sets of simple graphs
	4.2 HR-recognizable sets of graphs
	4.3 VR-equational sets of simple graphs
	4.4 VR-recognizable sets of simple graphs
	4.5 HR-and VR-equational and recognizable sets
	4.6 References
5 Monadic second-order logic
	5.1 Relational structures and logical languages
	5.2 Graph properties expressible in monadic second-order logic
	5.3 Monadic second-order logic and recognizability
	5.4 Decidable monadic second-order theories
	5.5 Logical characterization of recognizability
	5.6 Equivalences of logical formulas
	5.7 References
6 Algorithmic applications
	6.1 Fixed-parameter tractable algorithms for model-checking
	6.2 Decomposition and parsing algorithms
	6.3 Monadic second-order formulas compiled into finite automata
	6.4 Other monadic second-order problems solved with automata
	6.5 References
7Monadic second-order transductions
	7.1 Definitions and basic properties
	7.2 The Equationality Theorem for the VR algebra
	7.3 Graph transductions using incidence graphs
	7.4 The Equationality Theorem for the HR algebra
	7.5 Decidability of monadic second-order satisfiability problems
	7.6 Questions about logical characterizations of recognizability
	7.7 References
8 Transductions of terms and words
	8.1 Terminology
	8.2 Tree-walking transducers
	8.3 The basic characterization
	8.4 From jumping to walking
	8.5 From global to local tests
	8.6 Multi bottom-up tree-to-word transducers
	8.7 Attribute grammars and macro tree transducers
	8.8 Nondeterminism
	8.9 VR-equational sets of terms and words
	8.10 References
9 Relational structures
	9.1 Two types of ternary relational structures related to ordered sets
	9.2 Relational structures of bounded tree-width
	9.3 Terms denoting relational structures
	9.4 Sparse relational structures
	9.5 References
Conclusion and open problems
References
Index of notation
Index