|
|
Please login using the form on menu list.
It is required to login for Full-Text PDF.
|
A Note on Probabilistic Rebound Automata
Lan ZHANG
Tokio OKAZAKI
Katsushi INOUE
Akira ITO
Yue WANG
Publication
IEICE TRANSACTIONS on Information and Systems Vol.E81-D No.10 pp.1045-1052
Publication Date: 1998/10/20
Online ISSN:
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata,Languages and Theory of Computing
Keyword:
probabilistic rebound automaton,
one-marker rebound automaton,
two-way nondeterministic one counter automaton,
context-free language,
closure property,
Full Text: PDF(685.1KB)
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 + .
|
|
