1-1hit |
Tsunehiro YOSHINAGA Katsushi INOUE Itsuo TAKANAMI
This paper investigates the accepting powers of one-way alternating multi-stack-counter automata (lamsca's) and one-way alternating multi-counter automata (lamsca's) which operate in realtime. For each k1, let 1ASCA (k, real) (1ACA(k, real)) denote the class of sets accepted by realtime one-way alternating k-stach-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-counter (k-counter) automata with only universal states. We first investigate a relationship between the accepting powers of realtime lamsca's (lamca's) with only universal states, with only existential states, and with full alternation. We then investigate hierarchical properties based on the numbers of counters and stackcounters, and show, for example, that for each k1, 1USCA(k+1, real)-1ASCA(k, real)φ and 1UCA(k+1, real)-1ACA(k, real)φ. We finally investigate a relationship between the accepting powers of realtime lamsca's and lamca's, and show, for example, that there are no i and j such that 1UCA(i, real)=1USCA(j, real), and 1USCA(k, real)-1ACA(k, real)φ for each k1.