Abstracts for the LGTDS workshop

ICGT Conference , Barcelona, October 2002

Graph polynomials and generating functions definable in Monadic Second Order Logic

J.A. Makowsky

Faculty of Computer Science
Technion - Israel Institute of Technology
Haifa 32000, Israel
Home page:   http://www.cs.technion.ac.il/~janos
Preprints:   http://www.cs.technion.ac.il/~admlogic/TR/readme.html


We look at various notions of MSOL definability for graph polynomials and generating functions and show how these can be exploited algorithmically. Typically, MSOL definability allows one to find linear recurrences for combinatorial functions, or to exploit dynamic programming approaches.

We shall discuss the limitations of these methods and less known applications.

An extended abstract is available in postscript here: http://www.cs.technion.ac.il/~admlogic/TR/2002/Stacs03.ps