{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,6]],"date-time":"2026-08-06T18:16:30Z","timestamp":1786040190996,"version":"3.56.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0939370"],"award-info":[{"award-number":["CCF-0939370"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1041\/08"],"award-info":[{"award-number":["1041\/08"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>We put forward a general theory of<jats:italic>goal-oriented communication<\/jats:italic>, where communication is not an end in itself, but rather a means to achieving some<jats:italic>goals<\/jats:italic>of the communicating parties. Focusing on goals provides a framework for addressing the problem of potential \u201cmisunderstanding\u201d during communication, where the misunderstanding arises from lack of initial agreement on what protocol and\/or language is being used in communication. In this context, \u201creliable communication\u201d means overcoming any initial misunderstanding between parties towards achieving a given goal. Despite the enormous diversity among the goals of communication, we propose a simple model that captures all goals.<\/jats:p><jats:p>In the simplest form of communication we consider, two parties, a<jats:italic>user<\/jats:italic>and a<jats:italic>server<\/jats:italic>, attempt to communicate with each other in order to achieve some goal of the user. We show that<jats:italic>any goal<\/jats:italic>of communication can be modeled mathematically by introducing a third party, which we call the<jats:italic>referee<\/jats:italic>, who hypothetically monitors the conversation between the user and the server and determines whether or not the goal has been achieved. Potential misunderstanding between the players is captured by allowing each player (the user\/server) to come from a (potentially infinite) class of players such that each player is unaware which instantiation of the other it is talking to. We identify a main concept, which we call<jats:italic>sensing<\/jats:italic>, that allows goals to be achieved even under misunderstanding. Informally,<jats:italic>sensing<\/jats:italic>captures the user's ability (potentially using help from the server) to simulate the referee's assessment on whether the communication is achieving the goal. We show that when the user can sense progress, the goal of communication can be achieved despite initial misunderstanding. We also show that in certain settings sensing is necessary for overcoming such initial misunderstanding.<\/jats:p><jats:p>Our results significantly extend the scope of the investigation started by Juba and Sudan (STOC 2008) who studied the foregoing phenomenon in the case of a single specific goal. Our study shows that their main suggestion, that misunderstanding can be detected and possibly corrected by focusing on the goal, can be proved in full generality.<\/jats:p>","DOI":"10.1145\/2160158.2160161","type":"journal-article","created":{"date-parts":[[2012,5,1]],"date-time":"2012-05-01T13:43:38Z","timestamp":1335879818000},"page":"1-65","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["A theory of goal-oriented communication"],"prefix":"10.1145","volume":"59","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brendan","family":"Juba","sequence":"additional","affiliation":[{"name":"Harvard University and MIT CSAIL, Cambridge, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"Microsoft Research New England, Cambridge, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228289"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Berners-Lee T. Hendler J. and Lassila O. 2001. The semantic web. Scientific American 34--43. Berners-Lee T. Hendler J. and Lassila O. 2001. The semantic web. Scientific American 34--43.","DOI":"10.1038\/scientificamerican0501-34"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73015"},{"key":"e_1_2_1_6_1","volume-title":"7th ITU Internet report","author":"Briggs P."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","volume-title":"Experience and Nature","author":"Dewey J.","DOI":"10.1037\/13377-000"},{"key":"e_1_2_1_8_1","unstructured":"Goldreich O. Juba B. and Sudan M. 2009. A theory of goal-oriented communication. Tech. rep. TR09-075 Electronic Colloquium on Computational Complexity (ECCC). Goldreich O. Juba B. and Sudan M. 2009. A theory of goal-oriented communication. Tech. rep. TR09-075 Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","volume-title":"Universal Artificial Intelligence","author":"Hutter M.","DOI":"10.1201\/9781003460299-10"},{"key":"e_1_2_1_12_1","volume-title":"Universal Semantic Communication","author":"Juba B."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science. 79--86","author":"Juba B."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374397"},{"key":"e_1_2_1_15_1","volume-title":"II: A theory of goal-oriented communication. Tech. rep. TR08-095, Electronic Colloquium on Computational Complexity (ECCC).","author":"Juba B.","year":"2008"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2nd Symposium on Innovations in Computer Science. 22--31","author":"Juba B."},{"key":"e_1_2_1_17_1","first-page":"277","article-title":"Semantic communication for simple goals is equivalent to on-line learning. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory","volume":"6925","author":"Juba B.","year":"2011","journal-title":"Lecture Notes in Artificial Intelligence Series"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_19_1","volume-title":"The Meaning of Meaning","author":"Malinowski B."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622826.1622844"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2006.62"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Uckelmann D. Harrison M. and Michahelles F. 2011. An architectural approach towards the future internet of things. In Architecting the Internet of Things D. Uckelmann M. Harrison and F. Michahelles Eds. Springer Berlin 1--24. Uckelmann D. Harrison M. and Michahelles F. 2011. An architectural approach towards the future internet of things. In Architecting the Internet of Things D. Uckelmann M. Harrison and F. Michahelles Eds. Springer Berlin 1--24.","DOI":"10.1007\/978-3-642-19157-2_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Uckelmann D. Harrison M. and Michahelles F. 2011b. Architecting the Internet of Things. Springer Berlin. Uckelmann D. Harrison M. and Michahelles F. 2011b. Architecting the Internet of Things. Springer Berlin.","DOI":"10.1007\/978-3-642-19157-2"},{"key":"e_1_2_1_26_1","volume-title":"The Blue and Brown Books: Preliminary Studies for the \u2018Philosophical Investigations\u2019","author":"Wittgenstein L."},{"key":"e_1_2_1_27_1","unstructured":"Wittgenstein L. 2001. Philosophical Investigations. Basil Blackwell Malden. Wittgenstein L. 2001. Philosophical Investigations. Basil Blackwell Malden."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2160158.2160161","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2160158.2160161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:50Z","timestamp":1750240490000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2160158.2160161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1145\/2160158.2160161"],"URL":"https:\/\/doi.org\/10.1145\/2160158.2160161","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4]]},"assertion":[{"value":"2011-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}