33 Search Results for "Sala, Pietro"

Volume

LIPIcs, Volume 318

31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

TIME 2024, October 28-30, 2024, Montpellier, France

Editors: Pietro Sala, Michael Sioutis, and Fusheng Wang

Document
DOI: 10.4230/LIPIcs.TIME.2025.8
Heuristics for Covering the Timeline in Temporal Graphs

Authors: Riccardo Dondi, Rares-Ioan Mateiu, and Alexandru Popa

Published in: LIPIcs, Volume 355, 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)

Abstract
We consider a variant of the Vertex Cover problem on temporal graphs, called Minimum Timeline Cover (k-MinTimelineCover). Temporal graphs are used to model complex systems, describing how edges (relations) change in a discrete time domain. The k-MinTimelineCover problem has been introduced in complex data summarization and synthesis jobs. Given a temporal graph G, k-MinTimelineCover asks to define k activity intervals for each vertex, such that each temporal edge is covered by at least one active interval. The objective function is the minimization of the sum of interval lengths. k-MinTimelineCover is NP-hard and even hard to approximate within any factor for k > 1. While the literature has mainly focused on the cases k = 1, in this contribution we consider the case k > 1. We first present an ILP formulation that is able to solve the problem on moderate size instances. Then we develop an efficient heuristic, based on local search which is built on top of the solution of an existing literature method. Finally, we present an experimental evaluation of our algorithms on synthetic data sets, that shows in particular that our heuristic has a consistent improvement on the state-of-the art method.
Cite as

Riccardo Dondi, Rares-Ioan Mateiu, and Alexandru Popa. Heuristics for Covering the Timeline in Temporal Graphs. In 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 355, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dondi_et_al:LIPIcs.TIME.2025.8,
  author =	{Dondi, Riccardo and Mateiu, Rares-Ioan and Popa, Alexandru},
  title =	{{Heuristics for Covering the Timeline in Temporal Graphs}},
  booktitle =	{32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-401-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{355},
  editor =	{Vidal, Thierry and Wa{\l}\k{e}ga, Przemys{\l}aw Andrzej},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2025.8},
  URN =		{urn:nbn:de:0030-drops-244542},
  doi =		{10.4230/LIPIcs.TIME.2025.8},
  annote =	{Keywords: Temporal Networks, Activity Timeline, Vertex Cover, Heuristic, Dynamic Programming}
}
Document
DOI: 10.4230/LIPIcs.TIME.2025.4
Assessing the (In)Ability of LLMs to Reason in Interval Temporal Logic

Authors: Pietro Bellodi, Pietro Casavecchia, Alberto Paparella, Guido Sciavicco, and Ionel Eduard Stan

Published in: LIPIcs, Volume 355, 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)

Abstract
The logical reasoning skills of Large Language Models (LLMs) is poorly understood and often overstated. Current evaluation suites rely on algebraic or commonsense puzzles that mix reasoning with symbolic manipulation and/or provide static datasets that quickly saturate or leak into pretraining corpora. In purely logical terms, the most relevant reasoning skill is the meta-mathematical task of valid formula recognition, which is at the foundation of higher-level reasoning tasks (including deduction and minimization of assertions, to name just a few). In the current landscape of LLMs benchmarking, puzzles are most often stated in propositional or first-order logic, with a few exceptions for point-based temporal logic, such as LTL; yet, in the real world, event-based temporal statements are prevalent, and they are more naturally expressed in interval-based temporal logic. Interval temporal logic offers a much richer (w.r.t. point-based temporal logic, for example) variety of problems, and not only do different languages present different expressive powers, but also the computational complexity of the validity problem can vary widely. In this paper, we tackle the problem of assessing the ability of LLMs to reason about interval-based statements in the form of validity recognition. We explore whether their accuracy is sensible to the underlying language, the computational complexity of the associated validity problem, and the intrinsic hardness of the problem in terms of formula length and modal depth of the problem. We benchmark several frontier LLMs (Gemma 3 27b It, Llama 4 Maverick, DeepSeek Chat V3 release 0324, Qwen 3 32b, and Qwen 3 235b) and show that, despite apparently impressive performance on algebraic or commonsense benchmarks, they falter on logically rigorous tasks.
Cite as

Pietro Bellodi, Pietro Casavecchia, Alberto Paparella, Guido Sciavicco, and Ionel Eduard Stan. Assessing the (In)Ability of LLMs to Reason in Interval Temporal Logic. In 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 355, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bellodi_et_al:LIPIcs.TIME.2025.4,
  author =	{Bellodi, Pietro and Casavecchia, Pietro and Paparella, Alberto and Sciavicco, Guido and Stan, Ionel Eduard},
  title =	{{Assessing the (In)Ability of LLMs to Reason in Interval Temporal Logic}},
  booktitle =	{32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-401-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{355},
  editor =	{Vidal, Thierry and Wa{\l}\k{e}ga, Przemys{\l}aw Andrzej},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2025.4},
  URN =		{urn:nbn:de:0030-drops-244504},
  doi =		{10.4230/LIPIcs.TIME.2025.4},
  annote =	{Keywords: Large Language Models, Benchmarking, Interval Temporal Logic}
}
Document
DOI: 10.4230/LIPIcs.TIME.2025.5
Higher-Order Timed Automata and Tail Recursion

Authors: Florian Bruse

Published in: LIPIcs, Volume 355, 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)

Abstract
Timed Automata (TA) are a popular formalism to model systems in dense linear time. However, due to their finite state-space, they can only model systems with a finitary logical behavior. There are extensions to e.g., timed pushdown systems and timed recursive state machines. Higher-Order Recursion Schemes (HORS) are another popular model for infinite-state, non-regular systems, naturally stratified by their type-theoretic order. We recently introduced Real-Time Recursion schemes as an approximation of HORS to real-time systems. This paper updates Real-Time Recursion Schemes into Higher-Order Timed Automata, a formalism that defines a tree-shaped timed automaton, which is more suitable to model actual systems. We show that the model-checking problem against the timed version of the modal mu-calculus exhibits the expected complexity bounds, i.e., an increase by one exponential towards the untimed version. We also show that, in the presence of tail recursion, half an exponential can be recovered, mirroring similar gains in the untimed setting. We also give a matching lower bound for the special case of order-1 HORTA. We conjecture that this can be generalized for all orders.
Cite as

Florian Bruse. Higher-Order Timed Automata and Tail Recursion. In 32nd International Symposium on Temporal Representation and Reasoning (TIME 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 355, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bruse:LIPIcs.TIME.2025.5,
  author =	{Bruse, Florian},
  title =	{{Higher-Order Timed Automata and Tail Recursion}},
  booktitle =	{32nd International Symposium on Temporal Representation and Reasoning (TIME 2025)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-401-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{355},
  editor =	{Vidal, Thierry and Wa{\l}\k{e}ga, Przemys{\l}aw Andrzej},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2025.5},
  URN =		{urn:nbn:de:0030-drops-244519},
  doi =		{10.4230/LIPIcs.TIME.2025.5},
  annote =	{Keywords: Timed Automata, Higher-Order Recursion Schemes, Tree Automata, Tail Recursion}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.TIME.2024
LIPIcs, Volume 318, TIME 2024, Complete Volume

Authors: Pietro Sala, Michael Sioutis, and Fusheng Wang

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
LIPIcs, Volume 318, TIME 2024, Complete Volume
Cite as

31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 1-308, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{sala_et_al:LIPIcs.TIME.2024,
  title =	{{LIPIcs, Volume 318, TIME 2024, Complete Volume}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{1--308},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024},
  URN =		{urn:nbn:de:0030-drops-220682},
  doi =		{10.4230/LIPIcs.TIME.2024},
  annote =	{Keywords: LIPIcs, Volume 318, TIME 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TIME.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Pietro Sala, Michael Sioutis, and Fusheng Wang

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sala_et_al:LIPIcs.TIME.2024.0,
  author =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.0},
  URN =		{urn:nbn:de:0030-drops-220672},
  doi =		{10.4230/LIPIcs.TIME.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.TIME.2024.1
A General Logical Approach to Learning from Time Series (Invited Talk)

Authors: Guido Sciavicco

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Machine learning from multivariate time series is a common task, and countless different approaches to typical learning problems have been proposed in recent years. In this talk, we review some basic ideas towards logic-based learning methods, and we sketch a general framework.
Cite as

Guido Sciavicco. A General Logical Approach to Learning from Time Series (Invited Talk). In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sciavicco:LIPIcs.TIME.2024.1,
  author =	{Sciavicco, Guido},
  title =	{{A General Logical Approach to Learning from Time Series}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{1:1--1:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.1},
  URN =		{urn:nbn:de:0030-drops-212088},
  doi =		{10.4230/LIPIcs.TIME.2024.1},
  annote =	{Keywords: Machine learning, temporal logic, general approach}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.TIME.2024.2
Strategic Reasoning Under Imperfect Information with Synchronous Semantics (Invited Talk)

Authors: Sophie Pinchinat

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Dynamic Epistemic Logic is a modal logic dedicated to specifying epistemic property changes along the dynamic behavior of a multi-agent system. The models that underlie this logic are (epistemic) states together with transitions caused by events, the occurrence of which may modify the current state. We first develop a setting where the entire dynamics of the system starting from an initial state is captured by a single infinite tree, in a way similar to what has been considered for Epistemic Temporal Logic, and second go through the current state-of-the-art regarding strategic reasoning, with a focus on planning problems in this infinite structure.
Cite as

Sophie Pinchinat. Strategic Reasoning Under Imperfect Information with Synchronous Semantics (Invited Talk). In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pinchinat:LIPIcs.TIME.2024.2,
  author =	{Pinchinat, Sophie},
  title =	{{Strategic Reasoning Under Imperfect Information with Synchronous Semantics}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.2},
  URN =		{urn:nbn:de:0030-drops-212093},
  doi =		{10.4230/LIPIcs.TIME.2024.2},
  annote =	{Keywords: Strategic reasoning, Imperfect information, chain-MSO, Automatic structures}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.TIME.2024.3
Rule-Based Temporal Reasoning: Exploring DatalogMTL (Invited Talk)

Authors: Przemysław Andrzej Wałęga

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
I will introduce DatalogMTL - an extension of Datalog, augmenting it with operators known from metric temporal logic (MTL). DatalogMTL is an expressive language which allows us for complex temporal reasoning over a dense timeline and, at the same time, remains decidable. I will provide an overview of research on DatalogMTL by discussing its computational complexity, syntactic and semantic modifications, practical reasoning approaches, applications, and future research directions.
Cite as

Przemysław Andrzej Wałęga. Rule-Based Temporal Reasoning: Exploring DatalogMTL (Invited Talk). In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 3:1-3:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{walega:LIPIcs.TIME.2024.3,
  author =	{Wa{\l}\k{e}ga, Przemys{\l}aw Andrzej},
  title =	{{Rule-Based Temporal Reasoning: Exploring DatalogMTL}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{3:1--3:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.3},
  URN =		{urn:nbn:de:0030-drops-212106},
  doi =		{10.4230/LIPIcs.TIME.2024.3},
  annote =	{Keywords: Temporal Datalog, Temporal Logic Programming, Temporal Reasoning}
}
Document
DOI: 10.4230/LIPIcs.TIME.2024.4
Agile Controllability of Simple Temporal Networks with Uncertainty and Oracles

Authors: Johann Eder, Roberto Posenato, Carlo Combi, Marco Franceschetti, and Franziska S. Hollauf

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Simple temporal networks with uncertainty (STNUs) have achieved wide attention and are the basis of many applications requiring the representation of temporal constraints and checking whether they are conflicting. Dynamic controllability is currently the most relaxed notion to check whether a system can be controlled without violating temporal constraints despite uncertainties. However, dynamic controllability assumes that the actual duration of a contingent activity is only known when the end event of this activity takes place. The recently introduced notion of agile controllability considers when this duration is known earlier, leading to a more relaxed notion of temporal feasibility. We extend the definition of STNUs to STNUOs (Simple Temporal Networks with Uncertainty and Oracles) to represent the point in time at which information about a contingent duration is available. We formally define agile controllability as a generalization of dynamic controllability considering the timepoints of information availability. We propose a set of constraint propagation rules for STNUOs leading to an algorithm for checking agile controllability.
Cite as

Johann Eder, Roberto Posenato, Carlo Combi, Marco Franceschetti, and Franziska S. Hollauf. Agile Controllability of Simple Temporal Networks with Uncertainty and Oracles. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{eder_et_al:LIPIcs.TIME.2024.4,
  author =	{Eder, Johann and Posenato, Roberto and Combi, Carlo and Franceschetti, Marco and Hollauf, Franziska S.},
  title =	{{Agile Controllability of Simple Temporal Networks with Uncertainty and Oracles}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.4},
  URN =		{urn:nbn:de:0030-drops-212115},
  doi =		{10.4230/LIPIcs.TIME.2024.4},
  annote =	{Keywords: Temporal constraint networks, contingent durations, agile controllability}
}
Document
DOI: 10.4230/LIPIcs.TIME.2024.5
Open the Chests: An Environment for Activity Recognition and Sequential Decision Problems Using Temporal Logic

Authors: Ivelina Stoyanova, Nicolas Museux, Sao Mai Nguyen, and David Filliat

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
This article presents Open the Chests, a novel benchmark environment designed for simulating and testing activity recognition and reactive decision-making algorithms. By leveraging temporal logic, Open the Chests offers a dynamic, event-driven simulation platform that illustrates the complexities of real-world systems. The environment contains multiple chests, each representing an activity pattern that an interacting agent must identify and respond to by pressing a corresponding button. The agent must analyze sequences of asynchronous events generated by the environment to recognize these patterns and make informed decisions. With the aim of theoretically grounding the environment, the Activity-Based Markov Decision Process (AB-MDP) is defined, allowing to model the context-dependent interaction with activities. Our goal is to propose a robust tool for the development, testing, and bench-marking of algorithms that is illustrative of realistic scenarios and allows for the isolation of specific complexities in event-driven environments.
Cite as

Ivelina Stoyanova, Nicolas Museux, Sao Mai Nguyen, and David Filliat. Open the Chests: An Environment for Activity Recognition and Sequential Decision Problems Using Temporal Logic. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{stoyanova_et_al:LIPIcs.TIME.2024.5,
  author =	{Stoyanova, Ivelina and Museux, Nicolas and Nguyen, Sao Mai and Filliat, David},
  title =	{{Open the Chests: An Environment for Activity Recognition and Sequential Decision Problems Using Temporal Logic}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.5},
  URN =		{urn:nbn:de:0030-drops-212128},
  doi =		{10.4230/LIPIcs.TIME.2024.5},
  annote =	{Keywords: Event-Based Decision Making, Activity Recognition, Temporal Logic, Reinforcement Learning, Dynamic Systems, Complex Event Processing, Benchmark Environment, Real-Time Simulation}
}
Document
DOI: 10.4230/LIPIcs.TIME.2024.6
Extending the Range of Temporal Specifications of the Run-Time Event Calculus

Authors: Periklis Mantenoglou and Alexander Artikis

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Composite event recognition (CER) frameworks reason over streams of low-level, symbolic events in order to detect instances of spatio-temporal patterns defining high-level, composite activities. The Event Calculus is a temporal, logical formalism that has been used to define composite activities in CER, while RTEC_{∘} is a formal CER framework that detects composite activities based on their Event Calculus definitions. RTEC_{∘}, however, cannot handle every possible set of Event Calculus definitions for composite activities, limiting the range of CER applications supported by RTEC_{∘}. We propose RTEC_{fl}, an extension of RTEC_{∘} that supports arbitrary composite activity specifications in the Event Calculus. We present the syntax, semantics, reasoning algorithms and time complexity of RTEC_{fl}. Our analysis demonstrates that RTEC_{fl} extends the scope of RTEC_{∘}, supporting every possible set of Event Calculus definitions for composite activities, while maintaining the high reasoning efficiency of RTEC_{∘}.
Cite as

Periklis Mantenoglou and Alexander Artikis. Extending the Range of Temporal Specifications of the Run-Time Event Calculus. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mantenoglou_et_al:LIPIcs.TIME.2024.6,
  author =	{Mantenoglou, Periklis and Artikis, Alexander},
  title =	{{Extending the Range of Temporal Specifications of the Run-Time Event Calculus}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.6},
  URN =		{urn:nbn:de:0030-drops-212135},
  doi =		{10.4230/LIPIcs.TIME.2024.6},
  annote =	{Keywords: Event Calculus, temporal pattern matching, composite event recognition}
}
Document
DOI: 10.4230/LIPIcs.TIME.2024.7
Fitting’s Style Many-Valued Interval Temporal Logic Tableau System: Theory and Implementation

Authors: Guillermo Badia, Carles Noguera, Alberto Paparella, Guido Sciavicco, and Ionel Eduard Stan

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Many-valued logics, often referred to as fuzzy logics, are a fundamental tool for reasoning about uncertainty, and are based on truth value algebras that generalize the Boolean one; the same logic can be interpreted on algebras from different varieties, for different purposes and pose different challenges. Although temporal many-valued logics, that is, the many-valued counterpart of popular temporal logics, have received little attention in the literature, the many-valued generalization of Halpern and Shoham’s interval temporal logic has been recently introduced and studied, and a sound and complete tableau system for it has been presented for the case in which it is interpreted on some finite Heyting algebra. In this paper, we take a step further in this inquiry by exploring a tableau system for Halpern and Shoham’s interval temporal logic interpreted on some finite {FL_{ew}}-algebra, therefore generalizing the Heyting case, and by providing its open-source implementation.
Cite as

Guillermo Badia, Carles Noguera, Alberto Paparella, Guido Sciavicco, and Ionel Eduard Stan. Fitting’s Style Many-Valued Interval Temporal Logic Tableau System: Theory and Implementation. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{badia_et_al:LIPIcs.TIME.2024.7,
  author =	{Badia, Guillermo and Noguera, Carles and Paparella, Alberto and Sciavicco, Guido and Stan, Ionel Eduard},
  title =	{{Fitting’s Style Many-Valued Interval Temporal Logic Tableau System: Theory and Implementation}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.7},
  URN =		{urn:nbn:de:0030-drops-212145},
  doi =		{10.4230/LIPIcs.TIME.2024.7},
  annote =	{Keywords: Interval temporal logic, many-valued logic, tableau system}
}
Document
DOI: 10.4230/LIPIcs.TIME.2024.8
A More Efficient and Informed Algorithm to Check Weak Controllability of Simple Temporal Networks with Uncertainty

Authors: Ajdin Sumic and Thierry Vidal

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Simple Temporal Networks with Uncertainty (STNU) are a well-known constraint-based model expressing sets of activities (e.g., a schedule or a plan) related by temporal constraints, each having possible durations in the form of convex intervals. Uncertainty comes from some of these durations being contingent, i.e., the agent executing the plan cannot decide the actual duration at execution time. To check that execution will satisfy all the constraints, three levels of controllability exist: the Strong and Dynamic Controllability (SC/DC) has proven both useful in practice and provable in polynomial time, while Weak Controllability (WC) is co-NP-complete and has been left aside. Moreover, controllability checking algorithms are propagation strategies, which have the usual drawback, in case of failure, to prove unable to locate the contingents that explain the source of non-controllability. This paper has three contributions: (1) it substantiates the usefulness of WC in multi-agent systems (MAS) where another agent controls a contingent, and agents agree just before execution on the durations; (2) it provides a new WC-checking algorithm whose performance in practice depends on the network structure and is faster in loosely connected ones; (3) it provides the failing cycles in the network that explain non-WC.
Cite as

Ajdin Sumic and Thierry Vidal. A More Efficient and Informed Algorithm to Check Weak Controllability of Simple Temporal Networks with Uncertainty. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sumic_et_al:LIPIcs.TIME.2024.8,
  author =	{Sumic, Ajdin and Vidal, Thierry},
  title =	{{A More Efficient and Informed Algorithm to Check Weak Controllability of Simple Temporal Networks with Uncertainty}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.8},
  URN =		{urn:nbn:de:0030-drops-212151},
  doi =		{10.4230/LIPIcs.TIME.2024.8},
  annote =	{Keywords: Temporal constraints satisfaction, uncertainty, STNU, Controllability checking, Explainable inconsistency, Multi-agent planning}
}
Document
DOI: 10.4230/LIPIcs.TIME.2024.9
A Faster Algorithm for Finding Negative Cycles in Simple Temporal Networks with Uncertainty

Authors: Luke Hunsberger and Roberto Posenato

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Temporal constraint networks are data structures for representing and reasoning about time (e.g., temporal constraints among actions in a plan). Finding and computing negative cycles in temporal networks is important for planning and scheduling applications since it is the first step toward resolving inconsistent networks. For Simple Temporal Networks (STNs), the problem reduces to finding simple negative cycles (i.e., no repeat nodes), resulting in numerous efficient algorithms. For Simple Temporal Networks with Uncertainty (STNUs), which accommodate actions with uncertain durations, the situation is more complex because the characteristic of a non-dynamically controllable (non-DC) network is a so-called semi-reducible negative (SRN) cycle, which can have repeat edges and, in the worst case, an exponential number of occurrences of such edges. Algorithms for computing SRN cycles in non-DC STNUs that have been presented so far are based on older, less efficient DC-checking algorithms. In addition, the issue of repeated edges has either been ignored or given scant attention. This paper presents a new, faster algorithm for identifying SRN cycles in non-DC STNUs. Its worst-case time complexity is O(mn + k²n + knlog n), where n is the number of timepoints, m is the number of constraints, and k is the number of actions with uncertain durations. This complexity is the same as that of the fastest DC-checking algorithm for STNUs. It avoids an exponential blow-up by efficiently dealing with repeated structures and outputting a compact representation of the SRN cycle it finds. The space required to compactly store accumulated path information while avoiding redundant storage of repeated edges is O(mk + k²n). An empirical evaluation demonstrates the effectiveness of the new algorithm on an existing benchmark.
Cite as

Luke Hunsberger and Roberto Posenato. A Faster Algorithm for Finding Negative Cycles in Simple Temporal Networks with Uncertainty. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hunsberger_et_al:LIPIcs.TIME.2024.9,
  author =	{Hunsberger, Luke and Posenato, Roberto},
  title =	{{A Faster Algorithm for Finding Negative Cycles in Simple Temporal Networks with Uncertainty}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.9},
  URN =		{urn:nbn:de:0030-drops-212160},
  doi =		{10.4230/LIPIcs.TIME.2024.9},
  annote =	{Keywords: Temporal constraint networks, overconstrained networks, negative cycles}
}
  • Refine by Type
  • 32 Document/PDF
  • 3 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 3 2025
  • 23 2024
  • 1 2023
  • 1 2021
  • 1 2020
  • Show More...

  • Refine by Author
  • 9 Sala, Pietro
  • 5 Bozzelli, Laura
  • 5 Montanari, Angelo
  • 5 Peron, Adriano
  • 4 Posenato, Roberto
  • Show More...

  • Refine by Series/Journal
  • 32 LIPIcs

  • Refine by Classification
  • 7 Computing methodologies → Temporal reasoning
  • 5 Theory of computation → Modal and temporal logics
  • 4 Theory of computation → Dynamic graph algorithms
  • 4 Theory of computation → Theory and algorithms for application domains
  • 3 Applied computing
  • Show More...

  • Refine by Keyword
  • 4 Temporal constraint networks
  • 3 Interval Temporal Logic
  • 3 Model Checking
  • 3 Satisfiability
  • 3 Tree Automata
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact