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
janos@cs.technion.ac.il
Home page:   http://www.cs.technion.ac.il/~janos
Preprints:   http://www.cs.technion.ac.il/~admlogic/TR/readme.html

Abstract

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