Graph Structure and Monadic Second-Order Logic: A by Professor Bruno Courcelle, Dr Joost Engelfriet

By Professor Bruno Courcelle, Dr Joost Engelfriet

The examine of graph constitution has complicated lately with nice strides: finite graphs may be defined algebraically, allowing them to be developed out of extra easy components. individually the houses of graphs should be studied in a logical language referred to as monadic second-order good judgment. during this booklet, those positive factors of graph constitution are introduced jointly for the 1st time in a presentation that unifies and synthesizes study over the past 25 years. the writer not just offers a radical description of the idea, but additionally info its purposes, at the one hand to the development of graph algorithms, and, at the different to the extension of formal language thought to finite graphs. for that reason the ebook should be of curiosity to graduate scholars and researchers in graph thought, finite version thought, formal language idea, and complexity idea.

Show description

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

Similar mathematics_1 books

Arithmétique et travaux pratiques cycle d'observation classe de sixième

Manuel de mathématiques, niveau sixième. Cet ouvrage fait partie de los angeles assortment Lebossé-Hémery dont les manuels furent à l’enseignement des mathématiques ce que le Bled et le Bescherelle furent à celui du français.

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

Example text

2 Some properties of series-parallel graphs We now show that fixed-point induction can also be used for proving universal properties of equational sets of graphs. 3: S = (S S) ∪ (S • S) ∪ {e}, where S ⊆ J2d . We will prove the assertions ∀G ∈ S. Pi (G), where the properties Pi are defined as follows: P1 (G) P2 (G) P3 (G) P4 (G) :⇐⇒ G is connected, :⇐⇒ G is bipolar, :⇐⇒ G is planar, :⇐⇒ G has no directed cycle. Adirected graph G with two sources denoted by srcG (1) and srcG (2) (cf. 3) is bipolar if it has no directed cycle and every vertex belongs to a directed path from srcG (1) to srcG (2).

The references section is organized in two parts: the first part (with reference labels starting with *) lists books, book chapters and survey articles. The second lists research articles and dissertations. All necessary definitions will be given, but the reader is expected to be familiar with the basic notions of Logic (mainly first-order logic), Universal Algebra (algebras, congruences), Formal Language Theory (context-free grammars, finite automata), and Graph Theory (basic notions). Chapters 2 to 9 present detailed proofs of results that have been published in articles.

Tρ( f ) ). This operation performs no computation; it combines its arguments which are terms into a larger term. For every F-algebra M, a term t ∈ T (F) has a value tM in M that is formally defined as follows: tM := fM if t = f and f has arity 0 (it is a constant symbol), tM := fM (t1M , . . , tρ( f )M ) if t = f (t1 , . . , tρ( f ) ). Since every term can be written in a unique way as f or f (t1 , . . , tρ( f ) ) for terms t1 , . . , tρ( f ) , the value tM of t is well defined. The mapping t → tM , also denoted by 6 For associative binary operations the more readable infix notation will be used, although it is ambiguous as already observed.

Download PDF sample

Rated 4.37 of 5 – based on 27 votes