Full Record

Author | Hunt, Alexis |

Title | Establishing a Connection Between Graph Structure, Logic, and Language Theory |

URL | http://hdl.handle.net/10012/9648 |

Publication Date | 2015 |

University/Publisher | University of Waterloo |

Abstract | The field of graph structure theory was given life by the Graph Minors Project of Robertson and Seymour, which developed many tools for understanding the way graphs relate to each other and culminated in the proof of the Graph Minors Theorem. One area of ongoing research in the field is attempting to strengthen the Graph Minors Theorem to sets of graphs, and sets of sets of graphs, and so on. At the same time, there is growing interest in the applications of logic and formal languages to graph theory, and a significant amount of work in this field has recently been consolidated in the publication of a book by Courcelle and Engelfriet. We investigate the potential applications of logic and formal languages to the field of graph structure theory, suggesting a new area of research which may provide fruitful. |

Subjects/Keywords | graph structure; logic; formal languages; language theory; monadic second-order logic; tree-decompositions; hyperedge replacement; HR algebra; graph theory; well-quasi-ordering; cone graph; cone ideal; tree-generator; obstruction-width |

Language | en |

Country of Publication | ca |

Record ID | handle:10012/9648 |

Repository | waterloo |

Date Retrieved | 2019-06-25 |

Date Indexed | 2019-06-26 |

Sample Search Hits | Sample Images | Cited Works

…8
F∪
fga (G)
14
19
forb(F )
Powerset signature of F
Graph obtained from G by forgetting the asource, if any
Ideal with *obstruction* set F
4
G
S(G)
Gconn
Collection of all graphs
Set of all subgraphs of G
Collection…

…to S
Vertex label of v
Set of rooted trees fully labeled from Q
15
10
26
MOD(φ)
M/∼
MS2
Set of all models of φ
Quotient algebra of M
Monadic second-order logic of all RG formulas
30
17
31
obs(C)
ow(I)
*Obstruction*…

…set of C
*Obstruction*-width of I
4
48
P(M)
P α (S)
Powerset algebra of M
Generalized powerset of S
14
5
r(T )
Root vertex of T
8
viii
Notation
Description
rena↔b (G)
RG
Graph obtained from G by…

…X α Y
G1 τ G2
ix
Page
List
19
31
10
8
19
9
9
37
5
24
1
1.1
Introduction
Motivation
The field of graph structre *theory* has grown considerably as a result of the Graph Minors Project of
Robertson and Seymour. Robertson and Seymour explored the…

…structural properties and relationships
of graphs, and the fruits of their research have led to advances in other fields, one of which is the study
of fixed-parameter tractable algorithms in complexity *theory*.
Possibly the most famous result to come out of…

…ordering, but it is equivalent to, after suitable definitions for limit ordinals, the ideals of order
up to the first uncountable ordinal being well-quasi-ordered [10]. Thomas later used category *theory* to
extend the result to apply to larger…

…x28;finite) graphs
better-quasi-ordered by the minor relation? If not, where in the taking of ideals does this fail?
The purpose of this work is to study the structure of graphs using techniques from language *theory*
and logic. The intersection of…

…these fields and graph *theory* is a growing area of study. Engelfriet and
Courcelle recently published a book [2] outlining many major results from their work in the area, and
it is this book which will serve as the basis for a lot of the…