Reconciling Communication Delays and Negation

Luís Cruz-Filipe*, Graça Gaspar, Isabel Nunes

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Hypothetical continuous query answering over data streams was introduced as a way to anticipate answers to queries that depend on facts that may or may not happen in the future. Previous work has studied this problem for Temporal Datalog with negation and instantaneous communication, showing that hypothetical answers can be incrementally updated as new data arrives at the data stream. In practice, individual communications take variable amounts of time, so data may arrive delayed and unordered. This motivates studying hypothetical continuous query answering in a setting with communication delays. The interaction between communication delays and negation is however problematic, and the existing approach is restricted to the positive fragment of the language. In this work we show how to remove this restriction by defining an appropriate operational semantics based on fixpoint theory, and showing that the relevant fixpoints can be computed in finite time by a carefully designed algorithm.

Original languageEnglish
Title of host publicationTheoretical Aspects of Computing – ICTAC 2022 - 19th International Colloquium, Proceedings
EditorsHelmut Seidl, Zhiming Liu, Corina S. Pasareanu
Number of pages19
PublisherSpringer Science+Business Media
Publication date2022
Pages151-169
ISBN (Print)9783031177149
DOIs
Publication statusPublished - 2022
Event19th International Colloquium on Theoretical Aspects of Computing, ICTAC 2022 - Tbilisi, Georgia
Duration: 27. Sep 202229. Sep 2022

Conference

Conference19th International Colloquium on Theoretical Aspects of Computing, ICTAC 2022
Country/TerritoryGeorgia
CityTbilisi
Period27/09/202229/09/2022
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13572 LNCS
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Reconciling Communication Delays and Negation'. Together they form a unique fingerprint.

Cite this