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

DOI10.1145/3604553MaRDI QIDQ6082230zbMATH OpenOpenAlexWikidataFDO

Authors Heba Aamer, Bart Bogaerts, Dimitri Surinx, Eugenia Ternovska, Jan Van den Bussche

Publication date 3 November 2023

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.06448

zbMATH Keywords

binary relations on valuationsdynamic logicexpressive power

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

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 paper 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.

Recommendations

• scientific article; zbMATH DE number 972605
• On the Logic of Information Flow
• scientific article; zbMATH DE number 873168
• scientific article; zbMATH DE number 700092
• The logic of information structures
• scientific article; zbMATH DE number 733404
• Logics of informational interactions
• Logics of Complementarity in Information Systems
• scientific article; zbMATH DE number 972578

Cites work

• An algebra of modular systems: static and dynamic perspectives
• Automatic behavior composition synthesis
• Cylindric algebras. Part II
• Dynamic predicate logic
• Executable First-Order Queries in the Logic of Information Flows
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 1395614 (Why is no real title available?)
• scientific article; zbMATH DE number 3359806 (Why is no real title available?)
• On the calculus of relations
• Relative expressive power of navigational querying on graphs
• Rewriting of regular expressions and regular path queries
• The relational model of data and cylindric algebras

Cited in

(1)

• Executable first-order queries in the logic of information flows

This page was built for publication: Inputs, Outputs, and Composition in the Logic of Information Flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6082230)