A Note on One-Way Multicounter Machines and Cooperating Systems of One-Way Finite Automata

Yue WANG  Katsushi INOUE  Itsuo TAKANAMI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.10   pp.1302-1306
Publication Date: 1993/10/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Automaton, Language and Theory of Computing
Keyword: 
one-way multicounter automata,  cooperating systems of one-way finite automata,  hierarchy,  computational complexity,  

Full Text: PDF(380.1KB)>>
Buy this Article




Summary: 
For each two positive integers r, s, let [1DCM(r)-Time(ns)] ([1NCM(r)-Time(ns)]) and [1DCM(r)-Space(ns)] ([1NCM(r)-Space(ns)]) be the classes of languages accepted in time ns and in space ns, respectively, by one-way deterministic (nondeterministic) r-counter machines. We show that for each X{D, N}, [1XCM(r)-Time(ns)][1XCM(r+1)-Time(ns)] and [1XCM(r)-Space(ns)][1XCM(r+1)-Space(ns)]. We also investigate the relationships between one-way multicounter machines and cooperating systems of one-way finite automata. In particular, it is shown that one-way (one-) counter machines and cooperating systems of two one-way finite automata are equivalent in accepting power.