The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability.

*(English)*Zbl 0754.68065This is the fifth in an ambitious series of papers exploring the possibilities of monadic second-order logic (MSOL) as a language for expressing properties of finite labelled hypergraphs (called simply graphs).

The central theme is the relationship between recognizability and MSO definability. The starting point is J. R. Büchi’s classical theorem which states that a string language is recognizable iff it is MSO definable. This result extends to tree languages, but for graphs just one half of it holds: MSO definable sets of graphs are recognizable. The author focuses on the converse implication. He conjectures that it would hold for graphs with bounded tree-width. He also notes the lack of a suitable notion of an automaton that would serve as an intermediate between congruences, in terms of which recognizability is defined, and MSO-formulas. However, if the graphs are generated by a context-free graph grammar, the derivation trees serve as structures that can be read by an automaton in a meaningful way. The main result states that for graph languages generated by so-called MSO parsable CF graph grammars, recognizability implies MSO definability. The paper contains also several further related notions, results and conjectures.

For Part IV see [B. Courcelle, Ann. Pure Appl. Logic 49, No. 3, 193–255 (1990; Zbl 0731.03006)].

The central theme is the relationship between recognizability and MSO definability. The starting point is J. R. Büchi’s classical theorem which states that a string language is recognizable iff it is MSO definable. This result extends to tree languages, but for graphs just one half of it holds: MSO definable sets of graphs are recognizable. The author focuses on the converse implication. He conjectures that it would hold for graphs with bounded tree-width. He also notes the lack of a suitable notion of an automaton that would serve as an intermediate between congruences, in terms of which recognizability is defined, and MSO-formulas. However, if the graphs are generated by a context-free graph grammar, the derivation trees serve as structures that can be read by an automaton in a meaningful way. The main result states that for graph languages generated by so-called MSO parsable CF graph grammars, recognizability implies MSO definability. The paper contains also several further related notions, results and conjectures.

For Part IV see [B. Courcelle, Ann. Pure Appl. Logic 49, No. 3, 193–255 (1990; Zbl 0731.03006)].

Reviewer: M.Steinby (Turku)

##### MSC:

68Q45 | Formal languages and automata |

68R10 | Graph theory (including graph drawing) in computer science |

03D05 | Automata and formal grammars in connection with logical questions |

68Q42 | Grammars and rewriting systems |

03B15 | Higher-order logic; type theory (MSC2010) |

PDF
BibTeX
XML
Cite

\textit{B. Courcelle}, Theor. Comput. Sci. 80, No. 2, 153--202 (1991; Zbl 0754.68065)

Full Text:
DOI

##### References:

[1] | Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graphs, (), 38-51 |

[2] | Bauderon, M.; Courcelle, B., Graph expressions and graph rewritings, Math. systems theory, 20, 83-127, (1987) · Zbl 0641.68115 |

[3] | Büchi, J., Weak second order logic and finite automata, S. math. logik grundlagen math., 5, 66-92, (1960) · Zbl 0103.24705 |

[4] | Courcelle, B., Equivalences and transformations of regular systems. applications to recursive program schemes and grammars, Theoret. comput. sci., 42, 1-122, (1986) · Zbl 0636.68104 |

[5] | Courcelle, B., Graph rewriting: an algebraic and logic approach, (), 193-242 · Zbl 0900.68282 |

[6] | Courcelle, B., The monadic second-order logic of graphs: definable sets of finite graphs, (), 30-53 |

[7] | Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs, Inform. and comput., 85, 12-75, (1990) · Zbl 0722.03008 |

[8] | Courcelle, B., The monadic second-order logic of graphs III: tree-decompositions minors, and complexity issues, (1990), submitted · Zbl 0754.03006 |

[9] | Courcelle, B., The monadic second-order logic of graphs IV: definability properties of equational graphs, Ann. pure appl. logic, 49, 193-255, (1990) · Zbl 0731.03006 |

[10] | Courcelle, B., On recognizable sets and tree-automata, (), 93-126 |

[11] | Doner, J., Tree acceptors and some of their applications, J. comput. system sci., 4, 406-451, (1970) · Zbl 0212.02901 |

[12] | Franchi-Zannettacci, P., Attributs sémantiques et schémas de programmes, () · Zbl 0523.68062 |

[13] | Gecseg, F.; Steinby, M., Tree-automata, (1984), Akademia Kaido Budapest · Zbl 0396.68041 |

[14] | Goguen, J.; Thatcher, J.; Wagner, E.; Wright, J., Initial algebra semantics and continuous algebras, J. ACM, 24, 68-95, (1977) · Zbl 0359.68018 |

[15] | Gohon, P., An algorithm to decide whether a rational subset of N^{λ} is recognizable, Theoret. comput. sci., 41, 51-59, (1985) · Zbl 0585.68072 |

[16] | Habel, A.; Kreowski, H.J., May we introduce to you: hyperedge replacement, (), 15-26 · Zbl 0643.68106 |

[17] | Leung, J.; Witthof, J.; Vornberger, O., On some variations on the bandwidth minimization problem, SIAM J. comput., 13, 650-667, (1984) · Zbl 0545.68058 |

[18] | Mezei, J.; Wright, J., Algebraic automata and context-free sets, Inform. and control, 11, 3-29, (1967) · Zbl 0155.34301 |

[19] | Montanari, U.; Rossi, F., An efficient algorithm for the solution of hierarchical networks of constraints, (), 440-457 |

[20] | Robertson, N.; Seymour, P., Some new results on the well-quasi-ordering of graphs, Ann. discrete math., 23, 343-354, (1984) |

[21] | D. Seese, The structure of the models of decidable monadic theories of graphs, Preprint 1987, Ann. Pure Appl. Logic, in press. · Zbl 0733.03026 |

[22] | Thomas, W., Automata on infinite objects, (), 133-191 · Zbl 0900.68316 |

[23] | Tutte, W., Graph theory, (1984), Addison-Wesley Reading, MA · Zbl 0554.05001 |

[24] | Valdes, J.; Lawler, E.; Tarjan, R., The recognition of series-parallel digraphs, SIAM J. comput., 11, 298-313, (1981) · Zbl 0478.68065 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.