{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:34:10Z","timestamp":1753889650399,"version":"3.41.2"},"reference-count":22,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2005,12,20]],"date-time":"2005-12-20T00:00:00Z","timestamp":1135036800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"funder":[{"name":"National Science Foundation","award":["0208535"],"award-info":[{"award-number":["0208535"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The framework of algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized knowledge algorithms. We then characterize the information provided by a randomized knowledge algorithm when its answers have some probability of being incorrect. We formalize this information in terms of evidence; a randomized knowledge algorithm returning ``Yes'' to a query about a fact \\phi provides evidence for \\phi being true. Finally, we discuss the extent to which this evidence can be used as a basis for decisions.<\/jats:p>","DOI":"10.2168\/lmcs-1(3:1)2005","type":"journal-article","created":{"date-parts":[[2006,11,23]],"date-time":"2006-11-23T09:25:09Z","timestamp":1164273909000},"source":"Crossref","is-referenced-by-count":2,"title":["Probabilistic Algorithmic Knowledge"],"prefix":"10.46298","volume":"Volume 1, Issue 3","author":[{"given":"Joseph Y.","family":"Halpern","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Pucella","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2005,12,20]]},"reference":[{"key":"10.2168\/LMCS-1(3:1)2005_r:berman89","doi-asserted-by":"crossref","unstructured":"Berman, P., J. Garay, and K. J. Perry (1989). Towards optimal distributed consensus. InProc. 30th IEEE Symposium on the Foundations of Computer Science (FOCS'89), pp. 410-415.","DOI":"10.1109\/SFCS.1989.63511"},{"key":"10.2168\/LMCS-1(3:1)2005_r:dolev83","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056650"},{"key":"10.2168\/LMCS-1(3:1)2005_FH","first-page":"39","volume":"34","author":"Fagin, R. and J. Y. Halpern (1988)","year":"1988","journal-title":"Artificial Intelligence"},{"issue":"1\/2","key":"10.2168\/LMCS-1(3:1)2005_FHM","first-page":"78","volume":"87","author":"Fagin, R., J. Y. Halpern, and N. Megiddo","year":"1990","journal-title":"Information and Computation"},{"key":"10.2168\/LMCS-1(3:1)2005_r:fagin95","doi-asserted-by":"crossref","unstructured":"Fagin, R., J. Y. Halpern, Y. Moses, and M. Y. Vardi (1995).Reasoning about Knowledge. MIT Press.","DOI":"10.7551\/mitpress\/5803.001.0001"},{"key":"10.2168\/LMCS-1(3:1)2005_Hal31","unstructured":"Halpern, J. Y. (2003).Reasoning About Uncertainty. Cambridge, Mass.: MIT Press."},{"key":"10.2168\/LMCS-1(3:1)2005_HF2","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0004-3702(92)90048-3","volume":"54","author":"Halpern, J. Y. and R. Fagin (1992)","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.2168\/LMCS-1(3:1)2005_r:halpern94","doi-asserted-by":"crossref","unstructured":"Halpern, J. Y., Y. Moses, and M. Y. Vardi (1994). Algorithmic knowledge. InProc. 5th Conference on Theoretical Aspects of Reasoning about Knowledge (TARK'94), pp. 255-266. Morgan Kaufmann.","DOI":"10.1016\/B978-1-4832-1453-5.50022-2"},{"key":"10.2168\/LMCS-1(3:1)2005_r:halpern02e","doi-asserted-by":"crossref","unstructured":"Halpern, J. Y. and R. Pucella (2002). Modeling adversaries in a logic for reasoning about security protocols. InProc. Workshop on Formal Aspects of Security (FASec'02), Volume 2629 ofLecture Notes in Computer Science, pp. 115-132.","DOI":"10.1007\/978-3-540-40981-6_11"},{"key":"10.2168\/LMCS-1(3:1)2005_r:halpern03b","unstructured":"Halpern, J. Y. and R. Pucella (2003). A logic for reasoning about evidence. InProc. 19th Conference on Uncertainty in Artificial Intelligence (UAI'03), pp. 297-304."},{"key":"10.2168\/LMCS-1(3:1)2005_Hi1","unstructured":"Hintikka, J. (1962).Knowledge and Belief. Ithaca, N.Y.: Cornell University Press."},{"key":"10.2168\/LMCS-1(3:1)2005_Hi2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00558761"},{"issue":"2","key":"10.2168\/LMCS-1(3:1)2005_r:kozen85","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/0022-0000(85)90012-1","volume":"30","author":"Kozen, D. (1985)","year":"1985","journal-title":"Journal of Computer and Systems Sciences"},{"key":"10.2168\/LMCS-1(3:1)2005_r:kripke63","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1002\/malq.19630090502","volume":"9","author":"Kripke, S. (1963)","year":"1963","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"10.2168\/LMCS-1(3:1)2005_r:kyburg83","unstructured":"Kyburg, Jr., H. E. (1983). Recent work in inductive logic. In T. Machan and K. Lucey (Eds.),Recent Work in Philosophy, pp. 87-150. Rowman & Allanheld."},{"key":"10.2168\/LMCS-1(3:1)2005_r:motwani95","doi-asserted-by":"crossref","unstructured":"Motwani, R. and P. Raghavan (1995).Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"issue":"1\/2","key":"10.2168\/LMCS-1(3:1)2005_r:paulson98","doi-asserted-by":"crossref","first-page":"85","DOI":"10.3233\/JCS-1998-61-205","volume":"6","author":"Paulson, L. C. (1998)","year":"1998","journal-title":"Journal of Computer Security"},{"key":"10.2168\/LMCS-1(3:1)2005_Rabin80","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"Rabin, M. O. (1980)","year":"1980","journal-title":"Journal of Number Theory"},{"issue":"1-3","key":"10.2168\/LMCS-1(3:1)2005_r:ramanujam99","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0168-0072(98)00045-1","volume":"96","author":"Ramanujam, R. (1999)","year":"1999","journal-title":"Annals of Pure and Applied Logic"},{"issue":"2","key":"10.2168\/LMCS-1(3:1)2005_RSA","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"Rivest, R. L., A. Shamir, and L. Adelman","year":"1978","journal-title":"Communications of the ACM"},{"key":"10.2168\/LMCS-1(3:1)2005_Shafer82","doi-asserted-by":"crossref","unstructured":"Shafer, G. (1982). Belief functions and parametric models (with commentary).Journal of the Royal Statistical Society, Series B } {\\em 44, 322-352.","DOI":"10.1111\/j.2517-6161.1982.tb01211.x"},{"issue":"4","key":"10.2168\/LMCS-1(3:1)2005_Walley87","doi-asserted-by":"crossref","first-page":"1439","DOI":"10.1214\/aos\/1176350603","volume":"18","author":"Walley, P. (1987)","year":"1987","journal-title":"Annals of Statistics"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/2261\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/2261\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T02:17:19Z","timestamp":1736648239000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/2261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,20]]},"references-count":22,"URL":"https:\/\/doi.org\/10.2168\/lmcs-1(3:1)2005","relation":{"is-same-as":[{"id-type":"arxiv","id":"cs\/0503018","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.cs\/0503018","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2005,12,20]]},"article-number":"2261"}}