Leaf-Size Bounded Real-Time Synchronized Alternating One-Way Multicounter Machines

Hiroshi MATSUNO  Katsushi INOUE  Itsuo TAKANAMI  

IEICE TRANSACTIONS on Information and Systems   Vol.E77-D   No.3   pp.351-354
Publication Date: 1994/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Automaton, Language and Theory of Computing
alternation,  synchronized alternation,  multicounter machine and real-time computation,  

Full Text: PDF>>
Buy this Article

This paper investigates the properties of synchronized alternating one-way multicounter machines (lsamcm's) which operate in real time (lsamcm-real's) and whose leaf-sizes are bounded by a constant or some function of the length of an input. Leaf-size reflects the number of processors which run in parallel in scanning a given input. We first consider the hieracrchies of lsamcm-real's based on the number of counters and constant leaf-sizes. We next show that lsamcm-real's are less powerful than lsamcm's which operate in linear time when the leaf-sizes of these machines are bounded by a function L(n) such that limn[L(n) log n/n]0 and L(n)2.