HIERARCHICAL PROPERTIES OF REALTIME ONE-WAY ALTERNATING MULTI-STACK-COUNTER AUTOMATA

This paper investigates the accepting powers of one-way alternating mu lti-stack-counter automata (lamsca's) and one-way alternating multi-co unter automata (lamca's) which operate in realtime. For each k greater -than-or-equal-to 1, let 1ASCA (k, real) (1ACA(k, real)) denote the cl ass of sets accepted by realtime one-way alternating k-stack-counter ( k-counter) automata, and let 1USCA(k, real) (1UCA(k, real)) denote the class of sets accepted by realtime one-way alternating k-stack-counte r (k-counter) automata with only universal states. We first investigat e a relationship between the accepting powers of realtime lamsca's (la mca's) with only universal states, with only existential states, and w ith full alternation. We then investigate hierarchical properties base d on the numbers of counters and stack-counters, and show, for example , that for each k greater-than-or-equal-to 1, 1USCA (k + 1, real) - 1A SCA(k, real) not-equal phi and 1UCA(k + 1, real) -1ACA (k, real) not-e qual phi. We finally investigate a relationship between the accepting powers of realtime lamsca's and lamca's, and show, for example, that t here are no i and j such that 1UCA(i, real) = 1USCA(j, real), and 1USC A(k, real) -1ACA (k, real) not-equal phi for each k greater-than-or-eq ual-to 1.