✦ LIBER ✦

On three-way two-dimensional multicounter automata

✍ Scribed by Andrzej Szepietowski

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 899 KB
Volume: 55
Category: Article
ISSN: 0020-0255
DOI: 10.1016/0020-0255(91)90004-e

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A relationship between two-dimensional f

A relationship between two-dimensional finite automata and three-way tape-bounded two-dimensional Turing machines

✍ Katsushi Inoue; Itsuo Takanami; Hiroshi Taniguchi 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 583 KB

On two-way tree automata

✍ Etsuro Moriya 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 323 KB

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

Optimal simulation of two-dimensional al

Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines

✍ Akira Ito; Katsushi Inoue; Itsuo Takanami; Yue Wang 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 633 KB

Notes on looping deterministic two-way p

Notes on looping deterministic two-way pushdown automata

✍ M. Ladermann; H. Petersen 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 444 KB

On the multiplying ability of two-way au

On the multiplying ability of two-way automata

✍ J.R.H. Dempster 📂 Article 📅 1968 🏛 Elsevier Science 🌐 English ⚖ 292 KB

It is shown that multiplication and square root extraction can be performed by the two-way automata of Kreider and Ritchie, thus answering questions raised by those authors. Square root extraction is straightforward (yielding an integer root and a remainder), but multiplication is achieved only by c