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.
翻译:信息流动的逻辑(LIF)是一个总的框架,在这个框架内,程序性质的任务可以以宣告性、逻辑性的方式模式化,本文件的第一项贡献是提出LIF表达式的投入和产出的语义和综合定义,我们研究了两者之间的关系,并表明我们的综合定义在准确的意义上是最佳的,第二个贡献是对LIF的顺序构成的表达力进行系统研究。我们在构成方面的结果将投入和产出的结果联系起来,并将LIF与一阶逻辑(FO)和可约束性可变性LIF与可约束性FO联系起来。