Ehrenfeucht–Fraïssé game

Ehrenfeucht - Fraisse games (EF games ) are a proof technique of model theory. By EF games can the equivalence of two structures show or refute. Structures are mostly used in descriptive complexity theory as a formalism for the description of objects, such as words or graphs. Ehrenfeucht - Fraisse games thus provide a tool for proving lower bounds, ie, to prove that a given class of structures can not be expressed by a certain logic.

They were developed by Andrzej Ehrenfeucht based on the theoretical work of the mathematician Roland Fraisse.

An EF game is played by two players, usually referred to by spoilers and duplicator ( by Joel Spencer ) or Samson and Delilah ( by Neil Immerman ).

• 3.1 SO ∃ games 3.1.1 Definition

• 3.2.1 definition
• 3.2.2 set

Designations

• Be a structure. Then call the appropriate universe (basic amount, amount of carrier ).
• STRUKT [ σ ] denote the set of all finite structures of signature σ.

The n -round EF game

Ehrenfeucht - Fraisse games in their traditional form are closely related to first-order logics. This basic shape is defined as follows.

Definition

Be

An n- round game is defined on the interpretations:

• In each round i (i
• If Samson has chosen an item, then selects Delilah in the same way any, otherwise a
• The resulting tuple is added to the initial amount.

• If a partial isomorphism is defined by this amount, Delilah has won, otherwise Samson has won.

Often applies; to write and the output set is empty.

Properties of EF- games

Set

Two structures are n- equivalent, Delilah wins.

Corollary

And are elementary equivalent.

Proving lower bounds

To prove that a set I ⊆ STRUKT [ σ ] can not be defined by FO [ σ ] - formulas, it suffices to show that there are two structures and are, for each n ∈, so that Delilah has a winning strategy for.

EF games for the second-order logic predicate

Ehrenfeucht - Fraisse games can be extended relatively easily to logics second stage. However, the evidence of winning strategies is in this case much more difficult. A restricted variant games for the existential predicate second-order logic ( ∃ SO, ESO). SO ∃ plays an important role in descriptive complexity theory through the characterization of the complexity class NP.

Confining the SO ∃ logic continues to monadic predicates ( ∃ MSO ), so this version of the EF games is equivalent to the Ajtai - Fagin games.

SO ∃ games

Definition

Be

The inputs for a SO ∃ game.

• Samson chooses the c predicates of arity over
• Delilah then selects the c predicates of arity over
• On the two extended structures finally the Ehrenfeucht - Fraisse game is played.

In MSO ∃ games ( restriction to monadic predicates ) holds for all i

Ajtai - Fagin games

Ajtai - Fagin games are equivalent in the sense and to the MSO ∃ games, as the Ajtai - Fagin that Delilah game on a set I ⊆ STRUKT [ σ ] if and only wins if for each c and each n two structures there, so that it gains the appropriate MSO ∃ game. However Ajtai - Fagin games are formally easier to handle than MSO ∃ games.

Definition

A Ajtai - Fagin game is played on a set of structures I ⊆ STRUKT [ σ ]:

• First, Samson chooses two numbers
• Delilah then selects a structure
• Samson chooses the monadic predicates
• Delilah now selects another structure as well as the monadic predicates
• Now the Ehrenfeucht - Fraisse game is played on the two extended structures

Set

Let I ⊆ STRUKT [ σ ].

Delilah wins the Ajtai - Fagin game on II is definable by MSO ∃ [ σ ] logic.