Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Special Session Talk:
From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials

Speaker: Johann A. Makowsky
Presentation: swansea.pdf

Abstract

We outline a general theory of graph polynomials
which covers all the examples we found in the vast literature.
We introduce the class of (hyper)graph polynomials definable
in second order logic, and outline a research program
for their classification in terms of definability
and complexity comsiderations, and various notions of reducibilities. 


websites: Arnold Beckmann 2006-04-21 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net