IEICE TRANSACTIONS on Information
A Note on Probabilistic Rebound Automata
Summary :
This paper introduces a probabilistic rebound automaton (pra), and investigates its accepting power and closure property. We show that (1) the class of languages recognized by pra's with error probability less than 1/2, PRA, is incomparable with the class of context-free languages, (2) there is a language accepted by a two-way nondeterministic one counter automaton, but not in PRA, and (3) there is a language accepted by a deterministic one-marker rebound automaton, but not in PRA. We also show that PRA is not closed under concatenation and Kleene + .
- Publication
- IEICE TRANSACTIONS on Information Vol.E81-D No.10 pp.1045-1052
- Publication Date
- 1998/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Automata,Languages and Theory of Computing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Lan ZHANG, Tokio OKAZAKI, Katsushi INOUE, Akira ITO, Yue WANG, "A Note on Probabilistic Rebound Automata" in IEICE TRANSACTIONS on Information,
vol. E81-D, no. 10, pp. 1045-1052, October 1998, doi: .
Abstract: This paper introduces a probabilistic rebound automaton (pra), and investigates its accepting power and closure property. We show that (1) the class of languages recognized by pra's with error probability less than 1/2, PRA, is incomparable with the class of context-free languages, (2) there is a language accepted by a two-way nondeterministic one counter automaton, but not in PRA, and (3) there is a language accepted by a deterministic one-marker rebound automaton, but not in PRA. We also show that PRA is not closed under concatenation and Kleene + .
URL: https://global.ieice.org/en_transactions/information/10.1587/e81-d_10_1045/_p
Copy
@ARTICLE{e81-d_10_1045,
author={Lan ZHANG, Tokio OKAZAKI, Katsushi INOUE, Akira ITO, Yue WANG, },
journal={IEICE TRANSACTIONS on Information},
title={A Note on Probabilistic Rebound Automata},
year={1998},
volume={E81-D},
number={10},
pages={1045-1052},
abstract={This paper introduces a probabilistic rebound automaton (pra), and investigates its accepting power and closure property. We show that (1) the class of languages recognized by pra's with error probability less than 1/2, PRA, is incomparable with the class of context-free languages, (2) there is a language accepted by a two-way nondeterministic one counter automaton, but not in PRA, and (3) there is a language accepted by a deterministic one-marker rebound automaton, but not in PRA. We also show that PRA is not closed under concatenation and Kleene + .},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - A Note on Probabilistic Rebound Automata
T2 - IEICE TRANSACTIONS on Information
SP - 1045
EP - 1052
AU - Lan ZHANG
AU - Tokio OKAZAKI
AU - Katsushi INOUE
AU - Akira ITO
AU - Yue WANG
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 1998
AB - This paper introduces a probabilistic rebound automaton (pra), and investigates its accepting power and closure property. We show that (1) the class of languages recognized by pra's with error probability less than 1/2, PRA, is incomparable with the class of context-free languages, (2) there is a language accepted by a two-way nondeterministic one counter automaton, but not in PRA, and (3) there is a language accepted by a deterministic one-marker rebound automaton, but not in PRA. We also show that PRA is not closed under concatenation and Kleene + .
ER -
English
