{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T11:15:45Z","timestamp":1773314145219,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540582014","type":"print"},{"value":"9783540485667","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58201-0_55","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:32:36Z","timestamp":1330270356000},"page":"23-34","source":"Crossref","is-referenced-by-count":5,"title":["On the computational power of probabilistic and faulty neural networks"],"prefix":"10.1007","author":[{"given":"Hava T.","family":"Siegelmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"3_CR1","first-page":"75","volume":"19","author":"L. Adelman","year":"1978","unstructured":"L. Adelman. Two theorems on random polynomial time. In IEEE Sympos. on Foundations of Computer Science, volume 19, pages 75\u201383, New-York, 1978.","journal-title":"IEEE Sympos. on Foundations of Computer Science"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity, volume I and II. Springer-Verlag EATCS Monographs, Berlin, 1988\u20131990.","DOI":"10.1007\/978-3-642-75357-2"},{"key":"3_CR3","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. G. Bennet","year":"1981","unstructured":"C. G. Bennet and J. Gill. Relative to a random oracle a, p a \u2260 np a \u2260 co-np a with probability 1. SIAM J. on Computing, 10:96\u2013113, 1981.","journal-title":"SIAM J. on Computing"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, R. Gavald\u00e0, H.T. Siegelmann, and E. D. Sontag. Some structural complexity aspects of neural computation. In IEEE Structure in Complexity Theory Conference, pages 253\u2013265, San Diego, CA, May 1993.","DOI":"10.1109\/SCT.1993.336521"},{"key":"3_CR5","first-page":"315","volume":"1","author":"J. L. Balc\u00e1zar","year":"1992","unstructured":"J. L. Balc\u00e1zar, M. Hermo, and E. Mayordomo. Characterizations of logarithmic advice complexity classes. Information Processing 92, IFIP Transactions A-12, 1:315\u2013321, 1992.","journal-title":"Information Processing 92, IFIP Transactions A-12"},{"key":"3_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: Np completeness, recursive functions, and universal machines. Bull. A.M.S., 21:1\u201346, 1989.","journal-title":"Bull. A.M.S."},{"key":"3_CR7","first-page":"59","volume":"13","author":"R. L. Dobrushin","year":"1977","unstructured":"R.L. Dobrushin and S.I. Ortyukov. Lower bound for the redundancy of selfcorrecting arrangement of unreliable functional elements. Problems info, Transmission, 13:59\u201365, 1977.","journal-title":"Problems info, Transmission"},{"key":"3_CR8","first-page":"346","volume":"13","author":"R. L. Dobrushin","year":"1977","unstructured":"R.L. Dobrushin and S.I. Ortyukov. Upper bound for the redundancy of selfcorrecting arrangement of unreliable functional elements. Problems info, Transmission, 13:346\u2013353, 1977.","journal-title":"Problems info, Transmission"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"J. Kilian and H.T. Siegelmann. On the power of sigmoid neural networks. In Proc. Sixth ACM Workshop on Computational Learning Theory, Santa Cruz, July 1993.","DOI":"10.1145\/168304.168321"},{"key":"3_CR10","first-page":"477","volume":"7","author":"A. A. Muchnik","year":"1962","unstructured":"A. A. Muchnik and S. G. Gindikin. The completeness of a system made up of non-reliable elements realizing a function of algebraic logic. Soviet Phys. Dokl, 7:477\u2013479, 1962.","journal-title":"Soviet Phys. Dokl"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"P. Orponen. Neural networks and complexity theory. In Proc. 17th Symposium on Mathematical Foundations of Computer Science, pages 50\u201361, 1992.","DOI":"10.1007\/3-540-55808-X_5"},{"key":"3_CR12","first-page":"247","volume":"13","author":"S. I. Ortyukov","year":"1978","unstructured":"S.I. Ortyukov. Synthesis of asymptotically nonredundant self-correcting arrangements of unreliable functional elements. Problems Inform. Tranmission, 13:247\u2013251, 1978.","journal-title":"Problems Inform. Tranmission"},{"key":"3_CR13","unstructured":"I. Parberry. Knowledge, understanding, and computational complexity. Technical Report CRPDC-92-2, Department of Computer Sciences, University of North Texas, Feb 1992."},{"key":"3_CR14","volume-title":"Introduction to Probabilistic Automata","author":"A. Paz","year":"1971","unstructured":"A. Paz. Introduction to Probabilistic Automata. Academic Press, New York, 1971."},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1109\/18.2628","volume":"34","author":"N. Pippenger","year":"1988","unstructured":"N. Pippenger. Reliable computation by formulae in the presence of noise. IEEE Trans. Inform. Theory, 34:194\u2013197, 1988.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"3_CR16","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1145\/65950.77248","volume":"36","author":"N. Pippenger","year":"1989","unstructured":"N. Pippenger. Invariance of complexity measure ofr networks with unreliable gates. J. ACM, 36:531\u2013539, 1989.","journal-title":"J. ACM"},{"key":"3_CR17","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1090\/pspum\/050\/1067764","volume":"5","author":"N. Pippenger","year":"1990","unstructured":"N. Pippenger. Developments in: The synthesis of reliable organisms from unreliable components. In Proc. of symposia in pure mathematics, volume 5, pages 311\u2013324, 1990.","journal-title":"Proc. of symposia in pure mathematics"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"C. E. Shannon. A mathematical theory of communication. Bell System Tech J., pages 379\u2013423, 623\u2013656, 1948.","DOI":"10.1002\/j.1538-7305.1948.tb00917.x"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"H. T. Siegelmann. On the computational power of faulty and asynchronous neural networks. Technical report, Bar-Ilan university, 1993.","DOI":"10.1007\/3-540-58201-0_55"},{"issue":"6","key":"3_CR20","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0893-9659(91)90080-F","volume":"4","author":"H. T. Siegelmann","year":"1991","unstructured":"H. T. Siegelmann and E. D. Sontag. Turing computability with neural nets. Appl. Math. Lett., 4(6):77\u201380, 1991.","journal-title":"Appl. Math. Lett."},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"H. T. Siegelmann and E. D. Sontag. On computational power of neural networks. J. Comp. Syst. Sci, to appear. Previous version appeared in Proc. Fifth ACM Workshop on Computational Learning Theory, pages 440\u2013449, Pittsburgh, July 1992.","DOI":"10.1145\/130385.130432"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"H. T. Siegelmann and E. D. Sontag. Analog computation via neural networks. Theoretical Computer Science, to appear. A preliminary version in: The second Israel Symposium on Theory of Computing and Systems, Natanya, Israel, June, 1993.","DOI":"10.1109\/ISTCS.1993.253479"},{"key":"3_CR23","first-page":"558","volume":"15","author":"D. Ulig","year":"1974","unstructured":"D. Ulig. On the synthesis of self-correcting schemes from functional elements with a small numer of reliable elements. Math. Notes. Acad. Sci. USSR, 15:558\u2013562, 1974.","journal-title":"Math. Notes. Acad. Sci. USSR"},{"key":"3_CR24","volume-title":"Automata Studies","author":"J. Neumann von","year":"1956","unstructured":"J. von Neumann. Probabilistic, logics and the synthesis of reliable organisms from unreliable components. In C.E. Shannon and J. McCarth, editors, Automata Studies. Princeton U. Press, Princeton, NJ, 1956."},{"key":"3_CR25","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2946.001.0001","volume-title":"Extrapolation, interpolation, and smoothing of stationary time series","author":"N. Wiener","year":"1949","unstructured":"N. Wiener. Extrapolation, interpolation, and smoothing of stationary time series. MIT Press, Cambridge, MA, 1949."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58201-0_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:23:23Z","timestamp":1742595803000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58201-0_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582014","9783540485667"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-58201-0_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}