Abstracts for the LGTDS workshop

ICGT Conference , Barcelona, October 2002

Partial orders, graph grammars and logic

P. Weil (joint work with B. Courcelle)

Université Bordeaux-1
350 cours de la Libération
33405 Talence Cedex, France
Home page:   http://www.labri.fr/Perso/~weil


Among numerous types of graph-generating mechanisms based on rewriting, some have been identified as context-free. Two main classes have emerged, the class of VR-context-free sets of simple labelled graphs, and the class of HR-context-free sets of ranked labelled hypergraphs.

These grammars are best presented as systems of mutually recursive equations defining sets of graphs or hypergraphs.  These equations are written with set union and set extension of operations like disjoint union, fusion of certain vertices, creation of edges, relabellings.  A large class of such operations is defined by quantifier-free first-order formulas [Courcelle-Makowsky].

Monadic second-order logic is an essential tool in this context.  It behaves with respect to context-free graph grammars like finite automata with respect to context-free (word) grammars [Courcelle 97]. More precisely MS-definability implies recognizability (by congruences) for relational structures [Courcelle 92] and in particular for graphs [Courcelle 97].  The converse is true for graphs of bounded tree-width [Lapoire 98]. Certain transformations of structures defined by MS-formulas called MS-transductions, are also very useful, as are rational transductions in the theory of context-free grammars.

This basic framework can be adapted to other combinatorial structures : combinatorial maps [Lapoire, Courcelle-Dussaux], traces, texts (i.e., words equipped with a linear order of letter occurrences which is unrelated with the natural one) [Hoogeboom-ten Pas], partial orders [Lodaya-Weil, Kuske], bi-ordered sets [Esik-Nemeth].

In this survey, we try to reduce certain notions relevant to partial orders, to related notions on graphs, in particular in the field of context-free grammars.

All partial orders are finite.

1.  Relational structures for partial orders

A partial order may be handled in two ways: either as the relational structure (A, <) , i.e., a transitive graph , or as the graph representing the Hasse diagram.  The second representation is not redundant, and hence more economical in terms of space requirement.

The same MS-properties can be expressed via both representations, but not the same FO-properties. This makes a difference, for instance, for aperiodic word languages, where there are two distinct classes of regular languages describable by FO formulas.

The mapping from (A, <) to its Hasse diagram is FO-definable.  The opposite mapping, namely transitive closure, requires MS logic.

2.  Linearization

Obviously, every partial order is embeddable in a linear order.  But is such a linear order definable in MS logic?
Not in general, but Courcelle gave conditions making this possible [Courcelle 96].  This is especially useful for traces, and gives alternative proofs to results by Ochmanski on recognizable sets of traces.

3.  Operations on partial orders

We examine two classical operations in terms of the operations dealt with in [Courcelle-Makowsky] over Hasse diagrams: parallel composition, which corresponds to the disjoint union of Hasse diagrams; and full relational structures series composition (non commutative) , which can be conveniently described if the Hasse diagrams are equipped with (FO-definable) predicates indicating the minimal and the maximal elements.

We also consider the substitution of a partial order for an element of a partial order (this operation yields the so-called modular decompositions) and other types of concatenation of partial orders, which can be obtained from the general framework of graph grammars, and we compare them with the operations found in the literature.

4.  Recognizability

Recognizability can be defined in several ways: either algebraically (existence of a finite congruence relative to certain operations) or in terms of finite-state automata.  The equivalence of recognizability and MS-definability is a basic question.  This equivalence holds for words, trees, traces.  The case of partial orders is reviewed.  A difficulty comes from the fact that finite-state automata capturing recognizability and MS-definability do not exist for graphs, contrary to  the cases of words, trees and traces (via asynchronous automata, as in Zielonka's fundamental theorem).


[Courcelle 92] B. Courcelle. The monadic second-order logic of graphs VII: graphs as relational structures, Theoretical Computer Science 101 (1992) 3-33.

[Courcelle 96] B. Courcelle.  The monadic second-order logic of graphs X: Linear orders, Theoretical Computer Science 160 (1996) 87-143.

[Courcelle 97] B. Courcelle.  The expression of graph properties and graph transformations in monadic second-order logic, Chapter 5 of the "Handbook of graph grammars and computing by graph transformations, Vol.  1 : Foundations", G. Rozenberg ed., World Scientific (New-Jersey, London), 1997, pp.  313-400.

[Courcelle-Dussaux] B. Courcelle, V. Dussaux.  Map genus, forbidden maps and monadic second-order logic, Electronic Journal of Combinatorics, to appear.

[Courcelle-Makowsky] B. Courcelle, J. Makowsky.  Fusion in relational structures and the verification of monadic second-order properties, Mathematical Structures in Computer Science 12 (2002) 203-235.

[Esik-Nemeth] Z. Esik, Z. Németh. Automata on series-parallel biposets, to appear.

[Hoogeboom-ten Pas] H.J. Hoogeboom, P. ten Pas. Monadic second-order definable text languages, Theory of Computing Systems 30 (1997) 335-354.

[Kuske] D. Kuske. Infinite series-parallel posets: logic and languages, in ICALP 2000, Lecture Notes in Computer Science 1853, Springer 2000, 648-662.

[Lapoire] D. Lapoire. Structuration des graphes planaires, Ph.D. Dissertation, Université de Bordeaux-1, 1996.

[Lapoire 98] D. Lapoire. Recoginzability equals monadic second-order definability for sets of graphs of bounded tree-width, in STACS 1998, Lecture Notes in Computer Science 1373, Springer 1998, 618-628.

[Lodaya-Weil] K. Lodaya, P. Weil. Rationality in algebras with a series operation, Information and Computation 171 (2001) 269-293.