𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Multitape one-way nonwriting automata

✍ Scribed by Patrick C. Fischer; Arnold L. Rosenberg

Publisher
Elsevier Science
Year
1968
Tongue
English
Weight
591 KB
Volume
2
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

The theory given by Rabin and Scott for one-tape finite automata is extended to cover machines with several input tapes which can be advanced independently under finite-state control.

πŸ“œ SIMILAR VOLUMES

Multitape finite automata with rewind in
Multitape finite automata with rewind instructions
✍ Arnold L. Rosenberg πŸ“‚ Article πŸ“… 1967 πŸ› Elsevier Science 🌐 English βš– 858 KB

The model of multitape finite automaton is generalized by allowing the automaton to rewind all its tapes simultaneously at any stage in its computation. This added capability is shown to yield the Boolean closure of the class of word relations defined by multitape finite automata. Several properties

Fast one-way cellular automata
Fast one-way cellular automata
✍ Andreas Klein; Martin Kutrib πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 333 KB

Space-bounded one-way cellular language acceptors (OCA) are investigated. The only inclusion known to be strict in their time hierarchy from real-time to exponential-time is between real-time and linear-time! We show the surprising result that there exists an inΓΏnite hierarchy of properly included O