Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time

Tsunehiro YOSHINAGA; Katsushi INOUE

Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time

Tsunehiro YOSHINAGA, Katsushi INOUE

Full Text Views

0

Cite this

Summary :

This paper investigates the accepting powers of deterministic, Las Vegas, self-verifying nondeterministic, and nondeterministic one-way multi-counter automata with time-bounds. We show that (1) for each k1, there is a language accepted by a Las Vegas one-way k-counter automaton operating in real time, but not accepted by any deterministic one-way k-counter automaton operating in linear time, (2) there is a language accepted by a self-verifying nondeterministic one-way 2-counter automaton operating in real time, but not accepted by any Las Vegas one-way multi-counter automaton operating in polynomial time, (3) there is a language accepted by a self-verifying nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any deterministic one-way multi-counter automaton operating in polynomial time, and (4) there is a language accepted by a nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any self-verifying nondeterministic one-way multi-counter automaton operating in polynomial time.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.5 pp.1207-1212

Publication Date: 2003/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Tsunehiro YOSHINAGA, Katsushi INOUE, "Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time" in IEICE TRANSACTIONS on Fundamentals, vol. E86-A, no. 5, pp. 1207-1212, May 2003, doi: .
Abstract: This paper investigates the accepting powers of deterministic, Las Vegas, self-verifying nondeterministic, and nondeterministic one-way multi-counter automata with time-bounds. We show that (1) for each k1, there is a language accepted by a Las Vegas one-way k-counter automaton operating in real time, but not accepted by any deterministic one-way k-counter automaton operating in linear time, (2) there is a language accepted by a self-verifying nondeterministic one-way 2-counter automaton operating in real time, but not accepted by any Las Vegas one-way multi-counter automaton operating in polynomial time, (3) there is a language accepted by a self-verifying nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any deterministic one-way multi-counter automaton operating in polynomial time, and (4) there is a language accepted by a nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any self-verifying nondeterministic one-way multi-counter automaton operating in polynomial time.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_5_1207/_p

Copy

@ARTICLE{e86-a_5_1207,
author={Tsunehiro YOSHINAGA, Katsushi INOUE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time},
year={2003},
volume={E86-A},
number={5},
pages={1207-1212},
abstract={This paper investigates the accepting powers of deterministic, Las Vegas, self-verifying nondeterministic, and nondeterministic one-way multi-counter automata with time-bounds. We show that (1) for each k1, there is a language accepted by a Las Vegas one-way k-counter automaton operating in real time, but not accepted by any deterministic one-way k-counter automaton operating in linear time, (2) there is a language accepted by a self-verifying nondeterministic one-way 2-counter automaton operating in real time, but not accepted by any Las Vegas one-way multi-counter automaton operating in polynomial time, (3) there is a language accepted by a self-verifying nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any deterministic one-way multi-counter automaton operating in polynomial time, and (4) there is a language accepted by a nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any self-verifying nondeterministic one-way multi-counter automaton operating in polynomial time.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1207
EP - 1212
AU - Tsunehiro YOSHINAGA
AU - Katsushi INOUE
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2003
AB - This paper investigates the accepting powers of deterministic, Las Vegas, self-verifying nondeterministic, and nondeterministic one-way multi-counter automata with time-bounds. We show that (1) for each k1, there is a language accepted by a Las Vegas one-way k-counter automaton operating in real time, but not accepted by any deterministic one-way k-counter automaton operating in linear time, (2) there is a language accepted by a self-verifying nondeterministic one-way 2-counter automaton operating in real time, but not accepted by any Las Vegas one-way multi-counter automaton operating in polynomial time, (3) there is a language accepted by a self-verifying nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any deterministic one-way multi-counter automaton operating in polynomial time, and (4) there is a language accepted by a nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any self-verifying nondeterministic one-way multi-counter automaton operating in polynomial time.
ER -