Iterated pushdown automata and sequences of rational numbers (Q2498918)

The authors of this interesting paper establish formal relations between pushdown automata of positive level and graph-theoretical tree structures. Use is made of various generalizations of M. O. Rabin's tree theorem due to A. Muchnik. Thus, the authors provide an alternative approach for establishing various decidability properties for this automata class. Note that this approach also provides extensions of the basic result of Büchi on the decidability of monadic second-order arithmetic. The reviewer points out that several of the results are easily extended to recursive pushdown automata and r.e. sequences of algebraic numbers. The bibliography contains 35 basic items.