Ehrenfeucht games for the imperfect information logic

SANTIAGO FIGUEIRA; DANIEL GORÍN; RAFAEL GRIMSON

FAMAF, Cordoba, Argentina

Congreso; Logic, Computability and Randomnes; 2004

We define an Ehrenfeucht-Fraïssé game for Lii, the imperfect information logic, and prove that it captures the notion of model-equivalence of “positive satisfaction” for this logic. Unlike classical first order logic, “negative satisfaction” must be studied separately. We show that our definition of Ehrenfeucht-Fraïssé game also captures this notion, for a general kind of formulas. Additionally, we discuss some variations on the rules of the Ehrenfeucht-Fraïssé game for Lii that affect “negative satisfaction” equivalence, leaving “positive satisfaction” equivalence unchanged. Using this result, we give necessary and sufficient conditions for a class of finite structures to be axiomatizable in Lii. Finally, we present a new normal form for this logic.