Some observations on 1-inkdot alternating multi-counter automata with sublinear space

Authors
Yoshinaga, T Xu, JL Inoue, K
Citation
T. Yoshinaga et al., Some observations on 1-inkdot alternating multi-counter automata with sublinear space, IEICE T INF, E83D(2), 2000, pp. 285-290
Citations number
8
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
ISSN journal
09168532 → ACNP
Volume
E83D
Issue
2
Year of publication
2000
Pages
285 - 290
Database
ISI
SICI code
0916-8532(200002)E83D:2<285:SOO1AM>2.0.ZU;2-X
Abstract
This paper investigates some fundamental properties of 2-way alternating mu lti-counter automata (2amca's) with only existential (universal) states whi ch have sublinear space and 1 inkdot. It is shown that for any function s(n ) greater than or equal to log n such that log s(n) = o(log n), s(n) space- bounded 1-inkdot 2amca's with only existential states are incomparable with the ones with only universal states, and the ones with only existential (u niversal) states are not closed under complementation.