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