Inputs, Outputs, and Composition in the Logic of Information Flows

Heba Aamer, Bart Bogaerts, Dimitri SURINX, Eugenia Ternovska, Jan Van Den Bussche

Research output: Contribution to journalArticlepeer-review

40 Downloads (Pure)

Abstract

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.

This article is the extended version of a paper presented at KR 2020 [2].
Original languageEnglish
Article number33
Pages (from-to)1-44
Number of pages44
JournalACM Transactions on Computational Logic
Volume24
Issue number4
DOIs
Publication statusPublished - 2023

Bibliographical note

Funding Information:
This research received funding from the Flemish Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen” programme, from FWO Flanders project G0D9616N, and from Natural Sciences and Engineering Research Council of Canada (NSERC). Jan Van den Bussche is partially supported by the National Natural Science Foundation of China (61972455). Heba Aamer is supported by the Special Research Fund (BOF) (BOF19OWB16).

Publisher Copyright:
© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.

Fingerprint

Dive into the research topics of 'Inputs, Outputs, and Composition in the Logic of Information Flows'. Together they form a unique fingerprint.

Cite this