CLOSURE PROPERTY OF SPACE-BOUNDED TWO-DIMENSIONAL ALTERNATING TURING MACHINES, PUSHDOWN AUTOMATA, AND COUNTER AUTOMATA

摘要

This paper investigates closure property of the classes of sets accepted by space- bounded two-dimensional alternating Turing machines 92-atm's) and space-bounded two-dimensional alternating pushdown automata (2-apda's), and space-bounded two- dimensional alternating counter automata (2-aca's). Let L(m,n):N~2→N (N denotes the set of all positive integers) be a function with two variables m(=the number of rows of input tapes) and n(=the number of columns of input tapes)