ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
RS -Machines with Almost Blank Tape
Full text PdfPdf (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): 15,   Citation Count: 2
Additional Information:

references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
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
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
Patrick C. Fischer, Multi-tape and infinite-state automata—a survey, Communications of the ACM, v.8 n.12, p.799-805, Dec. 1965

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic


General Terms:
Performance, Theory, Verification

Collaborative Colleagues:
C. C. Elgot: colleagues
J. D. Rutledge: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player