Hierarchical Properties of Realtime One-Way Alternating Multi-Stack-Counter Automata (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
This paper investigates the accepting powers of one-way alternating multi-stack-counter automata (1amsca's) and one-way alternating multi-counter automata (1amca's) which operate in realtime. For each k≧1, let 1ASCA(k,real)(1ACA(k,real)) denote the class 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-counter (k-counter) automata with only universal states. We first investigate a relationship between the accepting powers of realtime lamsca's (1amca'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 stack-counters, and show, for example, that for each k≧1, 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 1amsca's and 1amca's, and show, for example, that there are no i and j such that UCA(i, real)=1USCA(j, real), and 1USCA(k, real)-1ACA(i, real)≠φ for each k≧1.
社団法人電子情報通信学会の論文
1994-04-25