✦ LIBER ✦

One-reversal counter machines and multihead automata: Revisited

✍ Scribed by Chiniforooshan, Ehsan; Daley, Mark; Ibarra, Oscar H.; Kari, Lila; Seki, Shinnosuke

Book ID: 119375319
Publisher: Elsevier Science
Year: 2012
Tongue: English
Weight: 231 KB
Volume: 454
Category: Article
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2012.04.002

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Remarks on multihead pushdown automata a

Remarks on multihead pushdown automata and multihead stack automata

✍ Satoru Miyano 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 660 KB

A note on semilinear sets and bounded-re

A note on semilinear sets and bounded-reversal multihead pushdown automata

✍ Oscar H. Ibarra 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 634 KB

Remarks on string-matching and one-way m

Remarks on string-matching and one-way multihead automata

✍ Marek Chrobak; Wojciech Rytter 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 357 KB

Remarks on sorting and one-way multihead

Remarks on sorting and one-way multihead finite automata

✍ Mirosław KutyŁowski 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 369 KB

On linear context-free languages and one

On linear context-free languages and one-way multihead automata

✍ Wojciech Rytter 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 321 KB

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