Full Record

New Search | Similar Records

Title Establishing a Connection Between Graph Structure, Logic, and Language Theory
Publication Date
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
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…