RS -Machines with Almost Blank Tape

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

RS -Machines with Almost Blank Tape

Full text

Pdf (1.68 MB)

Source

Journal of the ACM (JACM) archive
Volume 11 , Issue 3 (July 1964) table of contents

Pages: 313 - 337

Year of Publication: 1964

ISSN:0004-5411

Authors

C. C. Elgot	International Business Machines Corporation, Watson Research Center, Yorktown Heights, New York
J. D. Rutledge	International Business Machines Corporation, Watson Research Center, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 17, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321229.321235 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ELGOT, C. C. Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc. 98, 1 (Jan. 1961), 21-51.
	2	DAvIs, MARTIN; PUTNAM, I-IILARY; AND ROBINSON, JULIA. The decision problem for exponential Diophantine equations. Ann. Malh. 74, 3 (Nov. 1961), 425-436.
	3	POST, E.L. A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946), 264-268.
	4	HILBERT, D. AND BERNAYS, P. Grundlagen der Mathematik. Edwards Brothers, Inc., Ann Arbor, Michigan, 1944: lithoprinted from German ed.
	5	BuCHI, J. RICHARD. Weak second-order arithmetic AND finite automata. Zeit. Math. Logih Grund. Math. 6 (1960), 66-92.
	6	MINSKY, MARVIN L. Recursive unsolvability of Post's problem of tAG and other topics in theory of Turing machines, Ann. Math. 74, 3 (Nov. 1961), 437-455.
	7	PRESEURGER, M. Uber die Vollstindigkeit eines gewissen Systems der Arithmetic ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. Sprawozdanie z I Kongresu Matematykow Krajow Slowianskich, pp. 92-101,395, Warsaw, 1930.
	8	RAEIN, M. O., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Develop. 8, 2 (April 1959), 114-125.
	9	KLEENE, STEPEHN COLE. Introd'uction to Metaznathe,matics. D. Van Nostrand Company, Inc., New York, 1952.

CITED BY 2

	Patrick C. Fischer, Multi-tape and infinite-state automata—a survey, Communications of the ACM, v.8 n.12, p.799-805, Dec. 1965
	Oscar H. Ibarra, Reversal-Bounded Multicounter Machines and Their Decision Problems, Journal of the ACM (JACM), v.25 n.1, p.116-133, Jan. 1978