Sublinear Space-Bounded Multi-Inkdot Alternating Multi-Counter Automata with Only Universal States

概要

論文の詳細を見る
This paper investigates a hierarchical property based on the number of inkdots in the accepting powers of sublinear space-bounded multi-inkdot two-way alternating multi-counter automata with only universal states. For each l>_-1, each m>_-0, and any function L(n), let weak-2UCA^m(l, L(n)) and strong-2UCA^m(l, L(n)) denote the classes of sets accepted by weakly and strongly L(n) space-bounded m-inkdot two-way alternating l-counter automata with only universal states, respectively. We show that for any function L(n) such log L(n)=o(log n), strong-2UCA^<m+1>(1, log n)-U_<1<_-1<∞>, weak-2UCA^m(l, L(n))≠φ. So, we have x-2UCA^m, (l, L(n))〓 x-2UCA^<m+1>(l, L(n)) for each l>_-1, each x∈{strong, weak} and any function L(n)>_-log n such that log L(n) = o(log n).
徳山工業高等専門学校の論文
2006-12-01