The Ground Tree Transducer Game with Identical Tree Automata

Article type: Research Article

Authors: Apró, János | Vágvölgyi, Sándor

Abstract: We study that version of the ground tree transducer game where the same tree automaton appears as the first and second component of the associated ground tree transducer. We give conditions which imply that Beta has a winning strategy. Furthermore, we show the following decidability result. Given a ground tree transducer game where the underlying tree automaton A cannot evaluate some tree into a state or A is deterministic, we can decide which player has a winning strategy. Moreover, whatever player has a winning strategy, we can effectively construct a partial recursive winning strategy for him.

Keywords: games, automata, rewrite systems

Journal: Fundamenta Informaticae, vol. 45, no. 3, pp. 157-172, 2001