Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.10146 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911151320727552 |
|---|---|
| author | van Noort, Mathijs Ongenae, Femke Bonte, Pieter |
| author_facet | van Noort, Mathijs Ongenae, Femke Bonte, Pieter |
| contents | Temporal reasoning in dynamic, data-intensive environments increasingly demands expressive yet tractable logical frameworks. Traditional approaches often rely on negation to express absence or contradiction. In such contexts, Negation-as-Failure is commonly used to infer negative information from the lack of positive evidence. However, open and distributed systems such as IoT networks or the Semantic Web Negation-as-Failure semantics become unreliable due to incomplete and asynchronous data. This has led to a growing interest in negation-free fragments of temporal rule-based systems, which preserve monotonicity and enable scalable reasoning.
This paper investigates the expressive power of negation-free MTL, a temporal logic framework designed for rule-based reasoning over time. We show that the "always" operators of MTL, often treated as syntactic sugar for combinations of other temporal constructs, can be eliminated using "once", "since" and "until" operators. Remarkably, even the "once" operators can be removed, yielding a fragment based solely on "until" and "since". These results challenge the assumption that negation is necessary for expressing universal temporal constraints, and reveal a robust fragment capable of capturing both existential and invariant temporal patterns. Furthermore, the results induce a reduction in the syntax of MTL, which in turn can provide benefits for both theoretical study as well as implementation efforts. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10146 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Syntactical Simplification of Temporal Operators in Negation-free MTL van Noort, Mathijs Ongenae, Femke Bonte, Pieter Logic in Computer Science Temporal reasoning in dynamic, data-intensive environments increasingly demands expressive yet tractable logical frameworks. Traditional approaches often rely on negation to express absence or contradiction. In such contexts, Negation-as-Failure is commonly used to infer negative information from the lack of positive evidence. However, open and distributed systems such as IoT networks or the Semantic Web Negation-as-Failure semantics become unreliable due to incomplete and asynchronous data. This has led to a growing interest in negation-free fragments of temporal rule-based systems, which preserve monotonicity and enable scalable reasoning. This paper investigates the expressive power of negation-free MTL, a temporal logic framework designed for rule-based reasoning over time. We show that the "always" operators of MTL, often treated as syntactic sugar for combinations of other temporal constructs, can be eliminated using "once", "since" and "until" operators. Remarkably, even the "once" operators can be removed, yielding a fragment based solely on "until" and "since". These results challenge the assumption that negation is necessary for expressing universal temporal constraints, and reveal a robust fragment capable of capturing both existential and invariant temporal patterns. Furthermore, the results induce a reduction in the syntax of MTL, which in turn can provide benefits for both theoretical study as well as implementation efforts. |
| title | On Syntactical Simplification of Temporal Operators in Negation-free MTL |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2509.10146 |