Descriptive Complexity and Semantically Defined Fragments of Ptime.
Martin Otto's abstract for FMT and ST meeting, 7 Jan 1999
Descriptive Complexity and Semantically Defined Fragments of Ptime.
Abstract
Martin Otto (RWTH-Aachen)
The "Logic for Ptime" issue, or the question whether recursive syntax
can be given for the class of precisely those properties of finite
structures which are of polynomial time complexity, is one of the
long-standing research incentives in finite model theory. While there
may be less hope to settle the overall question in the positive, a few
interesting fragments of Ptime have emerged, defined in terms of
stronger invariance conditions than the obvious isomorphism
invariance, for which the issue could be settled positively. This is
achieved in a combination of techniques based on logical games,
concise invariants derived from these, and combinatorial canonization
procedures. In this talk I will focus on the general ideas and
techniques, their successes and limitations, and discuss one
particularly neat case in point, namely a capturing result for the
"modal" fragment as defined by the condition of bisimulation
invariance.