{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T16:29:24Z","timestamp":1673108964419},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1991,4]]},"abstract":"\n Let\n K<\/jats:italic>\n (\n m<\/jats:italic>\n ) denote the smallest number with the property that every\n m<\/jats:italic>\n -state finite automaton can be built as a neural net using\n K<\/jats:italic>\n (\n m<\/jats:italic>\n ) or fewer neurons. A counting argument shows that\n K<\/jats:italic>\n (\n m<\/jats:italic>\n ) is at least \u03a9((\n m<\/jats:italic>\n log\n m<\/jats:italic>\n )\n 1\/3<\/jats:sup>\n ), and a construction shows that\n K<\/jats:italic>\n (\n m<\/jats:italic>\n ) is at most\n O<\/jats:italic>\n (\n m<\/jats:italic>\n 3\/4<\/jats:sup>\n ). The counting argument and the construction allow neural nets with arbitrarily complex local structure and thus may require neurons that themselves amount to complicated networks. Mild, and in practical situations almost necessary, constraints on the local structure of the network give, again by a counting argument and a construction, lower and upper bounds for\n K<\/jats:italic>\n (\n m<\/jats:italic>\n ) that are both linear in\n m<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/103516.103523","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"495-514","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":68,"title":["Efficient simulation of finite automata by neural nets"],"prefix":"10.1145","volume":"38","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel-Aviv Univ., Tel-Aviv, Israel"}]},{"given":"A. K.","family":"Dewdney","sequence":"additional","affiliation":[{"name":"Univ. of Western Ontario, London, Ont., Canada"}]},{"given":"Teunis J.","family":"Ott","sequence":"additional","affiliation":[{"name":"Bell Communications Research, Morristown, NJ"}]}],"member":"320","published-online":{"date-parts":[[1991,4]]},"reference":[{"key":"e_1_2_1_1_2","first-page":"227","volume-title":"Proceedings of the 8th SouthEastern Conference on Combinatorics, Graph Theory and Computing","author":"DEWDNEY A. K.","unstructured":"DEWDNEY , A. K. Threshold matrices and the state assignment problem for neural nets . in Proceedings of the 8th SouthEastern Conference on Combinatorics, Graph Theory and Computing . Louisiana State University, Baton Rouge, La. , pp. 227 - 245 . DEWDNEY, A. K. Threshold matrices and the state assignment problem for neural nets. in Proceedings of the 8th SouthEastern Conference on Combinatorics, Graph Theory and Computing. Louisiana State University, Baton Rouge, La., pp. 227-245."},{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1017\/S0013091500011925","article-title":"The number of partitions of a set of n points m k dimensions induced by hyperplanes","volume":"15","author":"HARDING E. F","year":"1966","unstructured":"HARDING , E. F . The number of partitions of a set of n points m k dimensions induced by hyperplanes . Proc. Edinburgh Math. Soc. II , 15 ( 1966-67 ), 285 - 289 . HARDING, E. F. The number of partitions of a set of n points m k dimensions induced by hyperplanes. Proc. Edinburgh Math. Soc. II, 15 (1966-67), 285-289.","journal-title":"Proc. Edinburgh Math. Soc. II"},{"key":"e_1_2_1_3_2","volume-title":"An Introduction to the Theory of Numbers","author":"HARDY G. H.","year":"1938","unstructured":"HARDY , G. H. , AND WRIGHT , E. M. An Introduction to the Theory of Numbers . Oxford University Press, Oxford , England , 1938 . HARDY, G. H., AND WRIGHT, E. M. An Introduction to the Theory of Numbers. Oxford University Press, Oxford, England, 1938."},{"key":"e_1_2_1_4_2","volume-title":"Introductzon to Automata Theory, Languages, and Computatton","author":"HOPCROFT J. E.","year":"1979","unstructured":"HOPCROFT , J. E. , AND ULLMAN , J. D. Introductzon to Automata Theory, Languages, and Computatton . Addison-Wesley , Reading, Mass ., 1979 . HOPCROFT, J. E., AND ULLMAN, J. D. Introductzon to Automata Theory, Languages, and Computatton. Addison-Wesley, Reading, Mass., 1979."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00339943","article-title":"computation of decisxons in optimization problems","volume":"52","author":"HOPFIELD J. J.","year":"1985","unstructured":"HOPFIELD , J. J. , AND TANK , D. W. 'N eural' computation of decisxons in optimization problems . Biological Cybernetics 52 ( 1985 ), 141 - 152 . HOPFIELD, J. J., AND TANK, D. W. 'Neural' computation of decisxons in optimization problems. Biological Cybernetics 52 (1985), 141-152.","journal-title":"Biological Cybernetics"},{"key":"e_1_2_1_6_2","first-page":"116","article-title":"Graphen und Matnzen","volume":"38","author":"NIG D","year":"1931","unstructured":"K() NIG , D . Graphen und Matnzen . Mat. Fiz. Lapok. 38 ( 1931 ), 116 - 119 . K()NIG, D. Graphen und Matnzen. Mat. Fiz. Lapok. 38 (1931), 116-119.","journal-title":"Mat. Fiz. Lapok."},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02478259","article-title":"A logical calculus of the ideas immanent in nervous activity","volume":"5","author":"CULLOUCH W. S.","year":"1943","unstructured":"Mc CULLOUCH . W. S. , AND PITTS , W . A logical calculus of the ideas immanent in nervous activity . Bull. Math. Biophysics , 5 ( 1943 ), 115 - 133 . McCULLOUCH. W. S., AND PITTS, W. A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophysics, 5 (1943), 115-133.","journal-title":"Bull. Math. Biophysics"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1002\/j.1538-7305.1955.tb03788.x","article-title":"A method for synthesizing sequential circuits","volume":"34","author":"MEALY G. H","year":"1955","unstructured":"MEALY , G. H . A method for synthesizing sequential circuits . Bell Syst. Tech. J. 34 ( 1955 ), 1045 - 1079 . MEALY, G. H. A method for synthesizing sequential circuits. Bell Syst. Tech. J. 34 (1955), 1045-1079.","journal-title":"Bell Syst. Tech. J."},{"key":"e_1_2_1_9_2","volume-title":"Neural Nets and the brain model problem. Ph.D dissertatxon","author":"MINSKY M. L.","year":"1954","unstructured":"MINSKY , M. L. Neural Nets and the brain model problem. Ph.D dissertatxon , Princeton Univ., Princeton , N.j., 1954 . (Available from University Microfilms , Ann Arbor, Mich.) MINSKY, M. L. Neural Nets and the brain model problem. Ph.D dissertatxon, Princeton Univ., Princeton, N.j., 1954. (Available from University Microfilms, Ann Arbor, Mich.)"},{"key":"e_1_2_1_10_2","volume-title":"Computation: Finite and Infinite Machines","author":"MINSKY M. L.","year":"1967","unstructured":"MINSKY , M. L. Computation: Finite and Infinite Machines . Prentice-Hall , New York , 1967 . MINSKY, M. L. Computation: Finite and Infinite Machines. Prentice-Hall, New York, 1967."},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","volume-title":"AND THE PDP RESEARCH GROUP. Parallel Distributed Processing, vols","author":"RUMELHART D. E.","year":"1986","unstructured":"RUMELHART , D. E. , MCCLELLAND . J. L. , AND THE PDP RESEARCH GROUP. Parallel Distributed Processing, vols . I and II. MIT Press , Cambridge, Mass ., 1986 . RUMELHART, D. E., MCCLELLAND. J. L., AND THE PDP RESEARCH GROUP. Parallel Distributed Processing, vols. I and II. MIT Press, Cambridge, Mass., 1986.","DOI":"10.7551\/mitpress\/5236.001.0001"},{"key":"e_1_2_1_12_2","volume-title":"The Complexity of Computing","author":"SAVAGE J. E.","year":"1987","unstructured":"SAVAGE , J. E. The Complexity of Computing , 2 nd ed. Krieger , Malabar, Fla ., 1987 . SAVAGE, J. E. The Complexity of Computing, 2nd ed. Krieger, Malabar, Fla., 1987.","edition":"2"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/103516.103523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:29:07Z","timestamp":1672244947000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/103516.103523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,4]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,4]]}},"alternative-id":["10.1145\/103516.103523"],"URL":"http:\/\/dx.doi.org\/10.1145\/103516.103523","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":[[1991,4]]},"assertion":[{"value":"1991-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}