Publications of years 1987-1996 classified by topics

Last update: January 2004

Recent works

[UA1] (with M.Bauderon), *Graph expressions and graph rewritings*,
Mathematical Systems Theory 20 (1987) 83-127 (Presented at CAAP, 1986, Nice)

[UA2]* On recognizable sets and tree automata *, in "Resolution
of equations in algebraic structures", M. Nivat, H. Ait-Kaci eds., Academic
Press, 1989, 93-126.

[UA3] *Recognizable sets of unrooted trees*, in "Tree automata
and Languages", M. Nivat , A. Podelski eds., Elsevier, 1992, pp.141-157

[UA4] *Recognizable sets of graphs: Equivalent definitions and closure
properties*, Mathematical Structure in Computer Science 4 (1994) 127-138.

[UA5] (with J. Lagergren),* Recognizable sets of graphs of bounded
tree-width*, Proceedings of a Dagstuhl seminar, January 1993, Lec. Notes
Comp. Sci.776, 1994, pp.138-152.

[UA6] (with J. Lagergren) *Equivalent definitions of recognizability
for sets of graphs of bounded tree-width*, Math. Structure in Comp. Sci.
6 (1996) 141-165.

[UA7] *Basic notions of Universal Algebra for language theory
and graph grammars*, Theoret. Comp. Sci., "Tutorial section", 163 (1996)
1-54.

**Graph grammars, graph rewriting**

[GG1] *An axiomatic definition of context-free rewriting and its application
to NLC graph grammars*, Theoretical Computer Science 55 (1987) 141-181
(Presented at STACS, 1988, Bordeaux).** See corrections.**

[GG2] *Graph rewriting : An algebraic and logic approach*, in "Handbook
of Theoretical Computer Science, Volume B", J. Van Leeuwen ed., Elsevier,1990,
pp.193-242. **See corrections and updates**.

[GG3] *Recursive queries and context-free graph grammars*, Theoret.
Comput. Sci. 78 (1991) 217-244.

[GG4] (with S.Arnborg, A. Proskurowski, D. Seese): *An algebraic
theory of graph reduction*, JACM 40 (1993) 1134-1164, (Presented at International
Workshop on Graph Grammars, Bremen, 1991, see Lec. Notes Comp. Sci. 532).

[GG5] (with J. Engelfriet, G. Rozenberg), *Handle-rewriting hypergraph
grammars*, J. Computer System Sci. 46 (1993) 218-270.

[GG6] *Structural properties of context-free sets of graphs generated
by vertex-replacement*, Information and Computation 116 (1995) 275-293.
(Presented at FCT 1993, Lec. Notes Comp. Sci. 710).

[GG7] (with J. Engelfriet), *A logical characterization of hypergraph
languages generated by hyperedge replacement grammars*, Mathematical System
Theory 28 (1995) 515-552.

**Monadic Second-order Logic**

[MSG1] *The monadic second-order logic of graphs I: Recognizable sets
of finite graphs*. Information and Computation 85 (1990) 12-75. (Presented
at International Workshop on Graph Grammars, Warrenton, Virginia, 1986; see
Lec. Notes Comp. Sci. 291)

[MSG2] *The monadic second-order logic of graphs II: Infinite graphs
of bounded width*, Mathematical Systems Theory, 21(1989)187-221.

[MSG3]* The monadic second-order logic of graphs III: Tree-decompositions,
minors and complexity issues*, Inform. Théor. et Applications 26
(1992) 257-286 (Presented at WG'88, Amsterdam).

[MSG4] *The monadic second-order logic of graphs IV, Definability
properties of equational graphs*, Annals Pure Applied Logic 49 (1990)
193-255 (presented at ICALP 1989, Stresa, Italy).

[MSG5]* The monadic second-order logic of graphs V : On closing the
gap between definability and recognizability*, Theor. Comput. Sci. 80
(1991) 153-202 (Invited lecture to MFCS 1989, Prorabka Kozubnik, Poland).

[MSG6] * The monadic second order logic of graphs VI: On several
representations of graphs by relational structures*, Discrete Applied
Mathematics, 54 (1994) 117-149, (Presented at LICS, 1990, Philadelphia). **See
corrections**.

[MSG7] *The monadic second order logic of graphs VII: Graphs as relational
structures*, Theoretical Computer Science, 101 (1992)3-33. (Presented
at International Workshop on Graph Grammars, Bremen, 1991)

[MSG8] *The monadic second order logic of graphs VIII: Orientations*,
Annals of Pure Applied Logic 72 (1995) 103-143 (Presented at LICS, 1993, Montreal).

[MSG9] *The monadic second order logic of graphs IX: Machines and
their behaviours*, Theoret. Comp. Sci. 151 (1995) 125-162.

[MSG10] *The monadic second-order logic of graphs X: Linear orderings*,
Theoret. Comp. Sci., 160 (1996) 87-143. (Presented at CSL'94, Kazimierz, Poland,
see Lec. Notes Comp. Sci. 933, and in a workshop on graph grammars, see
"Graph Grammars and their applications to Computer Science", Lec. Notes Comput.
Sci. 1073).

[MS1] *Graphs and monadic second order logic : some open problems*,
invited paper ("The Logic in Computer Science Column" by Y. Gurevich), in
"Bulletin of EATCS",n°49, February 1993.

[MS2] (with M. Mosbah), *Monadic second-order evaluations of tree-decomposable
graphs*, Theoretical Computer Sci. 109 (1993) 49-82 (presented at International
Workshop on Graph Grammar, Bordeaux, 1991).

[MS3] *Monadic-second order graph transductions: a survey*,
(Invited Lecture at CAAP, 1992, Rennes), Theoret. Comput. Sci. 126 (1994)
53-75.

**Graph Theory, Minors**

[GT1] *On constructing obstruction sets of words*, Bulletin of
EATCS n° 44, 1991, pp. 178-185

[GT2] *Graph grammars, monadic second-order logic and the theory
of graph minors*, in "Graph Structure Theory", N. Robertson et P. Seymour
eds., Contemporary Mathematics (Amer. Math. Soc.) 147 (1993) 565-590.

[GT3] (with Y. Métivier), *Coverings and minors, application
to local computations in graphs*, European Journal of Combinatorics 5
(1994) 127-138.

[GT4] (with A.Pariès), *Mineurs d'arbres avec racines*, Informatique
Théorique et Applications 29 (1995) 401-422.

**Program schemes, language theory and other topics**

[Z1] *Fundamental properties of infinite trees*, Theoret. Comput.
Sci. 25 (1983), 69-95.

[Z2] *Equivalences and transformations of regular systems. Applications
to recursive program schemes and grammars*, Theoret. Comput. Sci. 42 (1986),
1-122.

[Z3] (with P. Deransart)* Proofs of partial correctness for attribute
grammars*, Information and Computation 78 (1988) 1-55.

[Z4] *A note on the minimalization of tree automata*, Proceedings
of 26th Semester of Banach Center, Warsaw, 1989, pp.197-203.

[Z5] *Recursive applicative program schemes*, in "Handbook of
Theoretical Computer Science, vol. B", Elsevier, 1990, pp.459-492.

[Z6] (with A.Podelski and D Niwinski), *A geometrical view of the
determinisation and minimisation of finite-state automata*, Mathematical
Systems Theory 24 (1991) 117-146.

[Z7] "Editor of": *Logique et Informatique, une introduction*, Actes
l'Ecole de Printemps d'Informatique Théorique de Albi, INRIA, collection
didactique, vol. 8, 1991