๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The Reduction of Two-Way Automata to One-Way Automata

โœ Scribed by Shepherdson, J. C.

Book ID
111980534
Publisher
IBM
Year
1959
Tongue
English
Weight
291 KB
Volume
3
Category
Article
ISSN
0018-8646

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 two-way tree automata
On two-way tree automata
โœ Etsuro Moriya ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 323 KB
On ywo-way, two-tape automata
On ywo-way, two-tape automata
โœ David Pager ๐Ÿ“‚ Article ๐Ÿ“… 1971 ๐Ÿ› Springer ๐ŸŒ English โš– 282 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