The Ground Tree Transducer Game

Abstract

We introduce the ground tree transducer game (gtt game) played by Alpha and Beta. We deduce from the possibility of embedding gtt games into abstract games that for any gtt game there is either a winning Alpha-strategy or a winning Beta-strategy. We present several examples for the game, and show that any abstract game can be simulated by some gtt game 𝒢, a set S₁ of Alpha-strategies for 𝒢, and a set S₂ of Beta-strategies for 𝒢. Among several decidability and undecidability results, we show the following. It is decidable, given gtt games 𝒢₁ and 𝒢₂, whether 𝒢₁ and 𝒢₂ are equivalent. There is no algorithm to determine, given a gtt game 𝒢 and an Alpha-strategy π, whether π is a winning Alpha-strategy. There is no algorithm to determine, given a recursive set S of gtt games, whether or not there exists a game 𝒢 ∈,; S such that Alpha has a winning strategy for 𝒢.