The Basic Algebra of Game Equivalences

We give a complete axiomatization of the identities of the basic game algebra valid with respect to the abstract game board semantics. We also show that the additional conditions of termination and determinacy of game boards do not introduce new valid identities. En route we introduce a simple translation of game terms into plain modal logic and thus translate, while preserving validity both ways, game identities into modal formulae. The completeness proof is based on reduction of game terms to a certain ‘minimal canonical form’, by using only the axiomatic identities, and on showing that the equivalence of two minimal canonical terms can be established from these identities.