{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2021,9,23]],"date-time":"2021-09-23T04:17:12Z","timestamp":1632370632251},"reference-count":9,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1968,7]]},"abstract":"A study of the problem of recognizing the set of primes by automata is presented. A simple algebraic condition is derived which shows that neither the set of primes nor any infinite subset of the set of primes can be accepted by a pushdown or finite automaton.<\/jats:p>\n In view of this result an interesting open problem is to determine the \u201cweakest\u201d automaton which can accept the set of primes. It is shown that the linearly bounded automaton can accept the set of primes, and it is conjectured that no automaton whose memory grows less rapidly can recognize the set of primes. One of the results shows that if this conjecture is true, it cannot be proved by the use of arguments about the distribution of primes, as described by the Prime Number Theorem. Some relations are established between two classical conjectures in number theory and the minimal rate of memory growth of automata which can recognize the set of primes.<\/jats:p>","DOI":"10.1145\/321466.321470","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:10Z","timestamp":1027769170000},"page":"382-389","source":"Crossref","is-referenced-by-count":27,"title":["On the Recognition of Primes by Automata"],"prefix":"10.1145","volume":"15","author":[{"given":"J.","family":"Hartmanis","sequence":"first","affiliation":[{"name":"Cornell University, Department of Computer Science, Ithaca, New York"}]},{"given":"H.","family":"Shank","sequence":"additional","affiliation":[{"name":"Cornell University, Department of Computer Science, Ithaca, New York"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","first-page":"78","volume-title":"Proc. Seventh Annual Symposium on Switching and Automata Theory, IEEE","author":"COBHAM A.","year":"1966"},{"key":"e_1_2_1_2_2","volume-title":"May 31, 1966.","author":"COBHAM A."},{"key":"e_1_2_1_3_2","first-page":"5","volume":"117","author":"HARTMANIS J.","year":"1965","journal-title":"Trans. Amer. Math. Soe."},{"key":"e_1_2_1_4_2","first-page":"5","volume":"74","author":"HARTMANIS J.","year":"1967","journal-title":"Amer. Math. Mon."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/321328.321337"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/321186.321196"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/321450.321461"},{"key":"e_1_2_1_8_2","volume-title":"McGraw-Hill","author":"HARRISON M.A.","year":"1965"},{"key":"e_1_2_1_9_2","first-page":"179","volume-title":"Proc. Sixth Annual Symposium on Switching Circuit Theory and Logical Design, IEEE","author":"STEARNS R. E.","year":"1965"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/321466.321470","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T23:50:35Z","timestamp":1614729035000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1968,7]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1968,7]]}},"alternative-id":["10.1145\/321466.321470"],"URL":"http:\/\/dx.doi.org\/10.1145\/321466.321470","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1968,7]]}}}