@InProceedings{   Pezzoli:CSL:1999,
  Author        = "Pezzoli, Elena",
  Editor        = "Gottlob, Georg and Grandjean, Etienne and Seyr, Katrin",
  Abstract      = {We show that deciding the winner of the r-moves Ehrenfeucht-Fra{\"\i}ss{\'e} game on two finite structures A and B, over any fixed signature $\Sigma$ that contains at least one binary and one ternary relation, is PSPACE complete. We consider two natural modifications of the EF game, the one-sided r-moves EF game, where the spoiler can choose from the first structure A only, and therefore the duplicator wins only if B satisfies all the existential formulas of rank at most r that A satisfies; and the k-alternations r-moves EF game (for each fixed k), where the spoiler can choose from either structure, but he can switch structure at most k times, and therefore the duplicator wins iff A and B satisfy the same first order formulas of rank at most r and quantifier alternation at most k (defined in the paper). We show that deciding the winner in both the one-sided EF game and the k-alternations EF game is also PSPACE complete.},
  Address       = "Berlin, Heidelberg",
  BookTitle     = "Proc. of CSL'99",
  date-added    = "2019-10-26 12:51:17 +0200",
  date-modified = "2019-10-26 12:51:33 +0200",
  ISBN          = "978-3-540-48855-2",
  Pages         = "159--170",
  Publisher     = "Springer Berlin Heidelberg",
  Title         = {Computational Complexity of Ehrenfeucht-Fra{\"\i}ss{\'e} Games on Finite Structures},
  Year          = "1999",
  File          = "Computational Complexity of Ehrenfeucht-Fraïssé Games on Finite Structures - Pezzoli1999\_Chapter\_ComputationalComplexityOfEhren - a - a - d.pdf"
}

@InProceedings{ Pezzoli:CSL:1999, Author = "Pezzoli, Elena", Editor = "Gottlob, Georg and Grandjean, Etienne and Seyr, Katrin", Abstract = {We show that deciding the winner of the r-moves Ehrenfeucht-Fra{\"\i}ss{\'e} game on two finite structures A and B, over any fixed signature $\Sigma$ that contains at least one binary and one ternary relation, is PSPACE complete. We consider two natural modifications of the EF game, the one-sided r-moves EF game, where the spoiler can choose from the first structure A only, and therefore the duplicator wins only if B satisfies all the existential formulas of rank at most r that A satisfies; and the k-alternations r-moves EF game (for each fixed k), where the spoiler can choose from either structure, but he can switch structure at most k times, and therefore the duplicator wins iff A and B satisfy the same first order formulas of rank at most r and quantifier alternation at most k (defined in the paper). We show that deciding the winner in both the one-sided EF game and the k-alternations EF game is also PSPACE complete.}, Address = "Berlin, Heidelberg", BookTitle = "Proc. of CSL'99", date-added = "2019-10-26 12:51:17 +0200", date-modified = "2019-10-26 12:51:33 +0200", ISBN = "978-3-540-48855-2", Pages = "159--170", Publisher = "Springer Berlin Heidelberg", Title = {Computational Complexity of Ehrenfeucht-Fra{\"\i}ss{\'e} Games on Finite Structures}, Year = "1999", File = "Computational Complexity of Ehrenfeucht-Fraïssé Games on Finite Structures - Pezzoli1999_Chapter_ComputationalComplexityOfEhren - a - a - d.pdf" }