Path-Bounded One-Way Multihead Finite Automata

Satoshi INOUE; Katsushi INOUE; Akira ITO; Yue WANG

doi:10.1093/ietisy/e88-d.1.96

Path-Bounded One-Way Multihead Finite Automata

Satoshi INOUE, Katsushi INOUE, Akira ITO, Yue WANG

Full Text Views

0

Share
Cite this

Summary :

For each positive integer r 1, a nondeterministic machine M is r path-bounded if for any input word x, there are r computation paths of M on x. This paper investigates the accepting powers of path-bounded one-way (simple) multihead nondeterministic finite automata. It is shown that for each k 2 and r 1, there is a language accepted by an (r + 1) path-bounded one-way nondeterministic k head finite automaton, but not accepted by any r path-bounded one-way nondeterministic k head finite automaton whether or not simple.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.1 pp.96-99

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.1.96

Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science)

Category

Cite this

Copy

Satoshi INOUE, Katsushi INOUE, Akira ITO, Yue WANG, "Path-Bounded One-Way Multihead Finite Automata" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 1, pp. 96-99, January 2005, doi: 10.1093/ietisy/e88-d.1.96.
Abstract: For each positive integer r 1, a nondeterministic machine M is r path-bounded if for any input word x, there are r computation paths of M on x. This paper investigates the accepting powers of path-bounded one-way (simple) multihead nondeterministic finite automata. It is shown that for each k 2 and r 1, there is a language accepted by an (r + 1) path-bounded one-way nondeterministic k head finite automaton, but not accepted by any r path-bounded one-way nondeterministic k head finite automaton whether or not simple.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.1.96/_p

Copy

@ARTICLE{e88-d_1_96,
author={Satoshi INOUE, Katsushi INOUE, Akira ITO, Yue WANG, },
journal={IEICE TRANSACTIONS on Information},
title={Path-Bounded One-Way Multihead Finite Automata},
year={2005},
volume={E88-D},
number={1},
pages={96-99},
abstract={For each positive integer r 1, a nondeterministic machine M is r path-bounded if for any input word x, there are r computation paths of M on x. This paper investigates the accepting powers of path-bounded one-way (simple) multihead nondeterministic finite automata. It is shown that for each k 2 and r 1, there is a language accepted by an (r + 1) path-bounded one-way nondeterministic k head finite automaton, but not accepted by any r path-bounded one-way nondeterministic k head finite automaton whether or not simple.},
keywords={},
doi={10.1093/ietisy/e88-d.1.96},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Path-Bounded One-Way Multihead Finite Automata
T2 - IEICE TRANSACTIONS on Information
SP - 96
EP - 99
AU - Satoshi INOUE
AU - Katsushi INOUE
AU - Akira ITO
AU - Yue WANG
PY - 2005
DO - 10.1093/ietisy/e88-d.1.96
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2005
AB - For each positive integer r 1, a nondeterministic machine M is r path-bounded if for any input word x, there are r computation paths of M on x. This paper investigates the accepting powers of path-bounded one-way (simple) multihead nondeterministic finite automata. It is shown that for each k 2 and r 1, there is a language accepted by an (r + 1) path-bounded one-way nondeterministic k head finite automaton, but not accepted by any r path-bounded one-way nondeterministic k head finite automaton whether or not simple.
ER -