Elena Pezzoli

On the classical and parametric complexity of the Ehrenfeucht-Fraisse
			    game. 


In the first part of the talk we present some results concerning the
complexity of the EF problem, that is the problem of determining the
winner of the r-moves Ehrenfeucht-Fraisse game on structures A and B over
signature Sigma: we show that the EF problem is hard for NP, and that the
one-sided EFP problem (where the spoiler can choose from structure A only)
and, for fixed k, the k-alternations EF problem (where the spoiler can
alternate at most k times; the spoiler makes an alternation in some round
of the game, if he chooses from a different structure than in the previous
round) are PSPACE complete. In the second part of the talk we introduce
the theory of fixed parameter tractability of Downey and Fellows and we
place the EF problem in the parametric hierarchy.