Concept

Ehrenfeucht fraisse game

A two-player game on a pair of structures whose outcome decides which sentences can tell them apart. Spoiler picks a point and Duplicator answers in the other structure, and surviving k rounds means no sentence of quantifier depth k separates them.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Also named here as quantifier depth — the same set of essays touches all of them, so they are one junction rather than several.

A 6-cycle and two 3-cycles: refinement cannot tell them apart. Two graphs side by side — one cycle and two smaller cycles — with the same number of points, the same number of edges and every point of the same degree.

The game the algorithm was playing

Change what Duplicator has to offer — a whole bijection instead of one element — and the game stops measuring first-order logic and starts measuring colour refinement, the algorithm every practical graph-isomorphism test begins with. Two subjects that grew apart are one game with the moves relabelled.

logic · Ehrenfeucht–Fraïssé games

Where a word of m letters stops being distinguishable from one of m + 1. A row for each quantifier depth and a cell for each length, shaded where Duplicator survives the game between words of that length and one longer.

A language that can name a set

Allow a sentence to quantify over sets of positions as well as positions, and on words the answer changes completely: the sets buy exactly the languages a finite automaton recognises. Whether the number of letters is even is the smallest example of what the sets are for.

logic · Ehrenfeucht–Fraïssé games

Named alongside it

The objects these essays reach for when they reach for this one.

Quantifier depth Colour refinement Exhaustive search Finite automaton Graph isomorphism Invariant Monoid Regular language Second-order logic

All concepts