𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Remarks on multihead pushdown automata and multihead stack automata

✍ Scribed by Satoru Miyano

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
660 KB
Volume
27
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On two-way multihead automata
On two-way multihead automata
✍ Oscar H. Ibarra πŸ“‚ Article πŸ“… 1973 πŸ› Elsevier Science 🌐 English βš– 479 KB

For each positive integer n, let -~eN(n ) be the class of sets accepted by a family of automata of type N, each with a read-only input with endmarkers and n two-way input heads. The following result, which is applicable to most types of two-way multihead devices, is proved: If for each positive inte

On tape-bounded complexity classes and m
On tape-bounded complexity classes and multihead finite automata
✍ I.H. Sudborough πŸ“‚ Article πŸ“… 1975 πŸ› Elsevier Science 🌐 English βš– 798 KB

The principal result described in this paper is the equivalence of the following statements : (1) Every set accepted by a nondeterministic one-way two-head finite automaton can be accepted by a deterministic two-way k-head finite automaton, for some k. (2) The context-free language Lp (described i

Checking automata and one-way stack lang
Checking automata and one-way stack languages
✍ Sheila Greibach πŸ“‚ Article πŸ“… 1969 πŸ› Elsevier Science 🌐 English βš– 837 KB

A checking automaton is equivalent to a one-way nonerasing stack automaton which, once it enters its stack, never again writes on its stack. The checking automaton languages (cal) form a full AFL closed under substitution. If L C a\* is an infinite cal, then L contains an infinite regular set. Conse