THE INFINITE TREE AUTOMATON

RABIN, M. O.

Decidability of Second-Order Theories and Automata on Infinite Trees.

Providence, Rhode Island, The American Mathematical Society, 1969. Royal8vo. In the original blue printed wrappers. In "Transactions of the American Mathematical Society", Volume 141, July, 1969. Entire issue offered. Spine faded and a few bumps to extremities, otherwise fine and clean. Pp. 1-35. [Entire volume: (4), 527 pp.].

First printing of Rabin's landmark paper in which he introduced his infinite tree automaton; a state machine that deals with infinite tree structure. It can be viewed as an extension from a finite tree automaton, which accepts only finite tree structures. Here he proved that the second-order theory of n successors is decidable; A key component of the proof implicitly showed determinacy of parity games, which lie in the third level of the Borel hierarchy.

It was used by Rabin for proving decidability of monadic second order logic. It has been further observed that tree automaton and logical theories are closely connected and it allows decision problems in logic to be reduced into decision problems for automaton.

Order-nr.: 49081