A Note on Alternating Multi-Counter Automata with Small Space

概要

論文の詳細を見る
This paper introduces space-bounded alternating multi-counter automata, and shows some fundamental properties of these automata. We first investigate relationships (1) between strong and weak space-bounds, (2) between one-way and two-way, and (3) among determinism, nondeterminism, and full alternation. Let weak-2ACA(k, L(n)) (weak-1ACA(k, L(n))) denote the class of sets accepted by weakly L(n) space-bounded two-way (one-way) alternating k-counter automata. We show, for example, that weak-2ACA(1, log n) - weak-1ACA (k, L(n)) ≠φ for any k ≥ 1 and any L(n) such that lim_<n→∞> [log L(n)/ log n] = 0. We then investigate a relationship between the accepting powers of multi-counter and multi-head finite automata. Let 2AFA(k) denote the class of sets accepted by two-way alternating k-head finite automata. We show, for example, that weak-2ACA(k, n) = 2AFA(k + 1) for each k ≥ 1. We finally investigate hierarchical properties based on the number of counters. Let weak-1UCA(k, L(n), real) denote the class of sets accepted by weakly L(n) space-bounded one-way alternating k-counter automata with only universal states which operate in realtime. We show, for example, that weak-1UCA(k+1, log n, real) - weak-1ACA(k, log n) ≠ φ for each k ≥ 1.
一般社団法人情報処理学会の論文
1995-12-15