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

Hiroshi MATSUNO; Katsushi INOUE; Itsuo TAKANAMI

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

Hiroshi MATSUNO, Katsushi INOUE, Itsuo TAKANAMI

Full Text Views

0

Share
Cite this

Summary :

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 lim_n[L(n) log n/n]0 and L(n)2.

Publication: IEICE TRANSACTIONS on Information Vol.E77-D No.3 pp.351-354

Publication Date: 1994/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: LETTER

Category: Automaton, Language and Theory of Computing

Cite this

Copy

Hiroshi MATSUNO, Katsushi INOUE, Itsuo TAKANAMI, "Leaf-Size Bounded Real-Time Synchronized Alternating One-Way Multicounter Machines" in IEICE TRANSACTIONS on Information, vol. E77-D, no. 3, pp. 351-354, March 1994, doi: .
Abstract: 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 lim_n[L(n) log n/n]0 and L(n)2.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e77-d_3_351/_p

Copy

@ARTICLE{e77-d_3_351,
author={Hiroshi MATSUNO, Katsushi INOUE, Itsuo TAKANAMI, },
journal={IEICE TRANSACTIONS on Information},
title={Leaf-Size Bounded Real-Time Synchronized Alternating One-Way Multicounter Machines},
year={1994},
volume={E77-D},
number={3},
pages={351-354},
abstract={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 lim_n[L(n) log n/n]0 and L(n)2.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - Leaf-Size Bounded Real-Time Synchronized Alternating One-Way Multicounter Machines
T2 - IEICE TRANSACTIONS on Information
SP - 351
EP - 354
AU - Hiroshi MATSUNO
AU - Katsushi INOUE
AU - Itsuo TAKANAMI
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 1994
AB - 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 lim_n[L(n) log n/n]0 and L(n)2.
ER -