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

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

doi:10.1145/3604553

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 journal › Article › peer-review

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 language	English
Article number	33
Pages (from-to)	1-44
Number of pages	44
Journal	ACM Transactions on Computational Logic
Volume	24
Issue number	4
DOIs	https://doi.org/10.1145/3604553
Publication status	Published - 2023

Access to Document

10.1145/3604553

InputsOutputsLIFAccepted author manuscript, 795 KB

VLAAI1: Subsidie: Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen
Nowe, A. & Vanderborght, B.
1/07/19 → 31/12/23
Project: Applied

Cite this

@article{a9c9b100cac44dd98bf30f349661dea1,

title = "Inputs, Outputs, and Composition in the Logic of Information Flows",

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].",

author = "Heba Aamer and Bart Bogaerts and Dimitri SURINX and Eugenia Ternovska and {Van Den Bussche}, Jan",

year = "2023",

doi = "10.1145/3604553",

language = "English",

volume = "24",

pages = "1--44",

journal = "ACM Transactions on Computational Logic",

issn = "1529-3785",

publisher = "ASSOC COMPUTING MACHINERY",

number = "4",

}

TY - JOUR

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

AU - Aamer, Heba

AU - Bogaerts, Bart

AU - SURINX, Dimitri

AU - Ternovska, Eugenia

AU - Van Den Bussche, Jan

PY - 2023

Y1 - 2023

N2 - 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].

AB - 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].

U2 - 10.1145/3604553

DO - 10.1145/3604553

M3 - Article

VL - 24

SP - 1

EP - 44

JO - ACM Transactions on Computational Logic

JF - ACM Transactions on Computational Logic

SN - 1529-3785

IS - 4

M1 - 33

ER -

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

Abstract

Access to Document

Fingerprint

Projects

VLAAI1: Subsidie: Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen

Cite this