{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:59Z","timestamp":1750219859916,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T00:00:00Z","timestamp":1692921600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Flemish Government under the \u201cOnderzoeksprogramma Artifici\u00eble Intelligentie (AI) Vlaanderen\u201d programme","award":["G0D9616N"],"award-info":[{"award-number":["G0D9616N"]}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61972455"],"award-info":[{"award-number":["61972455"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100007229","name":"Special Research Fund","doi-asserted-by":"crossref","award":["BOF19OWB16"],"award-info":[{"award-number":["BOF19OWB16"]}],"id":[{"id":"10.13039\/501100007229","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>The logic of information flows (LIF) is a general framework in which tasks of a procedural nature can be modeled in a declarative, logic-based fashion. The first contribution of this article is to propose semantic and syntactic definitions of inputs and outputs of LIF expressions. We study how the two relate and show that our syntactic definition is optimal in a sense that is made precise. The second contribution is a systematic study of the expressive power of sequential composition in LIF. Our results on composition tie in the results on inputs and outputs and relate LIF to first-order logic (FO) and bounded-variable LIF to bounded- variable FO.<\/jats:p>\n          <jats:p>\n            This article is the extended version of a paper presented at KR 2020\u00a0[\n            <jats:xref ref-type=\"bibr\">2<\/jats:xref>\n            ].\n          <\/jats:p>","DOI":"10.1145\/3604553","type":"journal-article","created":{"date-parts":[[2023,7,15]],"date-time":"2023-07-15T09:42:17Z","timestamp":1689414137000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Inputs, Outputs, and Composition in the Logic of Information Flows"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0460-8534","authenticated-orcid":false,"given":"Heba","family":"Aamer","sequence":"first","affiliation":[{"name":"Vrije Universiteit Brussel, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3460-4251","authenticated-orcid":false,"given":"Bart","family":"Bogaerts","sequence":"additional","affiliation":[{"name":"Vrije Universiteit Brussel, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0718-8854","authenticated-orcid":false,"given":"Dimitri","family":"Surinx","sequence":"additional","affiliation":[{"name":"Hasselt University, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0751-4031","authenticated-orcid":false,"given":"Eugenia","family":"Ternovska","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0072-3252","authenticated-orcid":false,"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[{"name":"Hasselt University, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,25]]},"reference":[{"key":"e_1_3_2_2_2","series-title":"Proceedings of the 23rd International Conference on Database Theory","first-page":"4:1\u20134:14","volume":"155","author":"Aamer Heba","year":"2020","unstructured":"Heba Aamer, Bart Bogaerts, Dimitri Surinx, Eugenia Ternovska, and Jan Van den Bussche. 2020. Executable first-order queries in the logic of information flows. In Proceedings of the 23rd International Conference on Database Theory(Leibniz International Proceedings in Informatics, Vol. 155). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 4:1\u20134:14."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2020\/1"},{"key":"e_1_3_2_4_2","first-page":"2646","volume-title":"AAAI Conference on Artificial Intelligence","author":"Alechina Natasha","year":"2019","unstructured":"Natasha Alechina, Tom\u00e1s Br\u00e1zdil, Giuseppe De Giacomo, Paolo Felli, Brian Logan, and Moshe Y. Vardi. 2019. Unbounded orchestrations of transducers for manufacturing. In AAAI Conference on Artificial Intelligence. AAAI Press, 2646\u20132653."},{"issue":"3","key":"e_1_3_2_5_2","first-page":"18","article-title":"Automatic service composition and synthesis: The Roman model","volume":"31","author":"Calvanese Diego","year":"2008","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Massimo Mecella, and Fabio Patrizi. 2008. Automatic service composition and synthesis: The Roman model. IEEE Data Eng. Bull. 31, 3 (2008), 18\u201322.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_3_2_6_2","first-page":"329","volume-title":"Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning.","author":"Calvanese Diego","year":"2016","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2016. Regular open APIs. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning.AAAI Press, 329\u2013338."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.12.001"},{"key":"e_1_3_2_8_2","volume-title":"Finite Model Theory (2nd ed.)","author":"Ebbinghaus Heinz-Dieter","year":"1999","unstructured":"Heinz-Dieter Ebbinghaus and J\u00f6rg Flum. 1999. Finite Model Theory (2nd ed.). Springer."},{"key":"e_1_3_2_9_2","volume-title":"A Mathematical Introduction to Logic","author":"Enderton Herbert B.","year":"1972","unstructured":"Herbert B. Enderton. 1972. A Mathematical Introduction to Logic. Academic Press."},{"key":"e_1_3_2_10_2","first-page":"51","volume-title":"Proceedings of the 33rd ACM Symposium on Principles of Database Systems","author":"Fan Wenfei","year":"2014","unstructured":"Wenfei Fan, Floris Geerts, and Leonid Libkin. 2014. On scale independence for querying big data. In Proceedings of the 33rd ACM Symposium on Principles of Database Systems. ACM, 51\u201362."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2014.11.031"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/3102713.3102745"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00628304"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.5"},{"key":"e_1_3_2_15_2","first-page":"1","volume-title":"Current Trends in Theoretical Computer Science","author":"Gurevich Yuri","year":"1988","unstructured":"Yuri Gurevich. 1988. Logic and the challenge of computer science. In Current Trends in Theoretical Computer Science, E. B\u00f6rger (Ed.). Computer Science Press, 1\u201357."},{"key":"e_1_3_2_16_2","volume-title":"Cylindric Algebras. Part I.","author":"Henkin Leon","year":"1971","unstructured":"Leon Henkin, J. Donald Monk, and Alfred Tarski. 1971. Cylindric Algebras. Part I.North-Holland."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90077-1"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04031-7","volume-title":"Constraint Databases","author":"Kuper Gabriel M.","year":"2000","unstructured":"Gabriel M. Kuper, Leonid Libkin, and Jan Paredaens (Eds.). 2000. Constraint Databases. Springer."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.2307\/2025310"},{"key":"e_1_3_2_20_2","first-page":"966","volume-title":"Proceedings of the 10th International Joint Conference on Artificial Intelligence","author":"Lifschitz Vladimir","year":"1987","unstructured":"Vladimir Lifschitz. 1987. Formal theories of action (preliminary report). In Proceedings of the 10th International Joint Conference on Artificial Intelligence, John P. McDermott (Ed.). Morgan Kaufmann, 966\u2013972. Retrieved from http:\/\/ijcai.org\/Proceedings\/87-2\/Papers\/081.pdf"},{"key":"e_1_3_2_21_2","first-page":"463","volume-title":"Machine Intelligence 4","author":"McCarthy John","year":"1969","unstructured":"John McCarthy and Patrick J. Hayes. 1969. Some philosophical problems from the standpoint of artificial intelligence. In Machine Intelligence 4, B. Meltzer and D. Michie (Eds.). Edinburgh University Press, 463\u2013502."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/5254.920599"},{"key":"e_1_3_2_23_2","first-page":"430","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Mitchell David G.","year":"2005","unstructured":"David G. Mitchell and Eugenia Ternovska. 2005. A framework for representing and solving NP search problems. In Proceedings of the AAAI Conference on Artificial Intelligence. AAAI Press\/The MIT Press, 430\u2013435."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.2307\/2268577"},{"key":"e_1_3_2_25_2","first-page":"275","volume-title":"Proceedings of the Global Conference on Artificial Intelligence","author":"Ternovska Eugenia","year":"2015","unstructured":"Eugenia Ternovska. 2015. An algebra of combined constraint solving. In Proceedings of the Global Conference on Artificial Intelligence. EasyChair, 275\u2013295."},{"key":"e_1_3_2_26_2","unstructured":"CEUR Workshop Proceedings Proceedings of the 11th Alberto Mendelzon International Workshop on Foundations of Data Management 1912 Eugenia Ternovska J. L. Reutter D. Srivastava Recent progress on the algebra of modular systems 2017"},{"key":"e_1_3_2_27_2","series-title":"Proceedings of the 12th Frontiers of Combining Systems Conference","first-page":"94","volume":"11715","author":"Ternovska Eugenia","year":"2019","unstructured":"Eugenia Ternovska. 2019. An algebra of modular systems: Static and dynamic perspectives. In Proceedings of the 12th Frontiers of Combining Systems Conference(Lecture Notes in Artificial Intelligence, Vol. 11715), A. Herzig and A. Popescu (Eds.). Springer, 94\u2013111."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604553","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604553","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:19Z","timestamp":1750178839000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604553"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,25]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3604553"],"URL":"https:\/\/doi.org\/10.1145\/3604553","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2023,8,25]]},"assertion":[{"value":"2022-09-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}