Lecture 12 (13.1.97)

Material of this and subsequent lectures:

[EFT] H.D. Ebbinghaus, J. Flum, Finite Model Theory, Springer 1994, Chapter 6.3

The theorems of Fagin, Immerman and Vardi

Let K be a class of finite ordered structures. Let c(K) denote the standard coding of K as a set of strings.

If c(K) is recognizable by a Turing machine which runs in polynomial space PSpace (in the size of the input structure) then K is definable in PFPL.
If c(K) is recognizable by a Turing machine which runs in non-deterministic polynomial time NP (in the size of the input structure) then K is definable in Existential SOL.
If c(K) is recognizable by a Turing machine which runs in polynomial time P (in the size of the input structure) then K is definable in IFPL.
If c(K) is recognizable by a Turing machine which runs in alternating logarithmic space AL (in the size of the input structure) then K is definable in FOL[ATC].
If c(K) is recognizable by a Turing machine which runs in non-determinsitic logarithmic space NL (in the size of the input structure) then K is definable in FOL[DTC].
If c(K) is recognizable by a Turing machine which runs in logarithmic space L (in the size of the input structure) then K is definable in FOL[DTC].

Detailed proof was given.