Inferring High-Level Events from Timestamped Data: Complexity and Medical Applications

Fleur Mougin; Katsumi Inoue; Meghyn Bienvenu; Vianney Jouhet; Yvon K. Awuklu

arxiv: 2604.21793 · v1 · submitted 2026-04-23 · 💻 cs.AI

Inferring High-Level Events from Timestamped Data: Complexity and Medical Applications

Yvon K. Awuklu , Meghyn Bienvenu , Katsumi Inoue , Vianney Jouhet , Fleur Mougin This is my paper

Pith reviewed 2026-05-09 21:50 UTC · model grok-4.3

classification 💻 cs.AI

keywords event detectiontemporal reasoninglogic programmingmedical dataanswer set programmingdata complexitylung cancerhigh-level events

0 comments

The pith

A logic-based framework infers high-level temporal events from timestamped data using rules and repairs, with polynomial data complexity under restrictions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a logic-based method to detect complex events that unfold over time from raw timestamped observations plus background knowledge. Rules define when simple events exist or end and how to combine them into meta-events such as disease episodes built from diagnoses and drug records. Constraints flag incompatible event combinations, and a repair step selects preferred consistent sets. Specific restrictions on the rules keep the reasoning polynomial in the size of the data. A prototype using answer set programming was tested on lung cancer patient records, where it ran efficiently and produced results that aligned with medical expert judgments.

Core claim

The framework employs logical rules to capture existence and termination conditions for simple temporal events and to combine these into meta-events; constraints identify incompatible combinations of events, and a repair mechanism selects preferred consistent sets. Reasoning in the full framework is intractable, but relevant restrictions ensure polynomial-time data complexity. The approach is evaluated on a lung cancer use case showing computational feasibility and alignment with expert opinions.

What carries the argument

Logical rules defining existence, termination, and composition of temporal events, combined with constraints and a repair mechanism for consistency.

If this is right

High-level events such as disease progressions become automatically detectable from standard timestamped clinical records.
The polynomial restrictions allow scaling to realistic volumes of medical data without exponential slowdown.
The same rule-and-repair structure can be reused in non-medical domains that record timestamped observations and domain constraints.
Incompatibilities between inferred events can be resolved systematically rather than left as unresolved contradictions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Integration with electronic health record systems could enable real-time flagging of candidate disease episodes for clinician review.
The repair mechanism could be extended with probabilistic preferences if domain experts supply likelihoods for competing event sets.
Rules might be partially learned from data rather than written entirely by hand, provided the polynomial restrictions are preserved.

Load-bearing premise

The provided rules and background knowledge must accurately capture the relevant domain events and incompatibilities so that the repair step selects sets matching real-world preferences.

What would settle it

Apply the system to a collection of patient records that have been independently annotated by multiple medical experts for the target high-level events, then measure whether the inferred events match the annotations at a rate significantly above random.

Figures

Figures reproduced from arXiv: 2604.21793 by Fleur Mougin, Katsumi Inoue, Meghyn Bienvenu, Vianney Jouhet, Yvon K. Awuklu.

**Figure 2.** Figure 2: Overview of the HEVA system architecture. B.1 Non-persistent Simple Event Module This module computes inferred non-persistent simple event facts from the predicates exists and terminates, following the formal construction of Definition 3. The computation proceeds by iterative interval construction with levelaware expansion and pruning. Initialization. For a non-persistent event predicate R ∈ RNS and arg… view at source ↗

read the original abstract

In this paper, we develop a novel logic-based approach to detecting high-level temporally extended events from timestamped data and background knowledge. Our framework employs logical rules to capture existence and termination conditions for simple temporal events and to combine these into meta-events. In the medical domain, for example, disease episodes and therapies are inferred from timestamped clinical observations, such as diagnoses and drug administrations stored in patient records, and can be further combined into higher-level disease events. As some incorrect events might be inferred, we use constraints to identify incompatible combinations of events and propose a repair mechanism to select preferred consistent sets of events. While reasoning in the full framework is intractable, we identify relevant restrictions that ensure polynomial-time data complexity. Our prototype system implements core components of the approach using answer set programming. An evaluation on a lung cancer use case supports the interest of the approach, both in terms of computational feasibility and positive alignment of our results with medical expert opinions. While strongly motivated by the needs of the healthcare domain, our framework is purposely generic, enabling its reuse in other areas.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a logic-based framework for inferring high-level temporal events from timestamped records using rules, meta-events, and constraint repair, with polynomial data complexity under restrictions and a lung cancer prototype that matches expert views.

read the letter

The main point is a practical logic programming setup for turning raw timestamps into higher-level events like disease episodes or therapies. Rules define when simple events start and end, meta-rules combine them, constraints flag incompatible sets, and a repair step picks consistent ones. They implement the core in answer set programming and test it on lung cancer records, where the output lines up with medical experts. The generic framing means it could apply to other timestamp logs too. The polynomial restrictions are the part that makes it usable at scale. That combination of temporal rules, repair, and complexity bounds is the actual new piece, even if it rests on prior logic programming work. The medical motivation is clear and the prototype shows the idea runs without blowing up. The evaluation is only sketched at high level, though, with no numbers on dataset size, runtime, or exact agreement rates, so it is hard to judge how robust the alignment really is. The specific restrictions that keep things polynomial are also not detailed in the summary, which leaves open how often they would hold in messy real records. This is for people working on temporal reasoning or medical data systems who want a rule-based alternative to pure machine learning. It is coherent on its own terms and addresses a genuine application gap, so it should go to referees for a full look at the proofs and experiments.

Referee Report

2 major / 2 minor

Summary. The paper develops a novel logic-based framework for inferring high-level temporally extended events from timestamped data and background knowledge. Logical rules capture existence and termination conditions for simple events and combine them into meta-events; constraints identify incompatibilities, and a repair mechanism selects preferred consistent sets. While full reasoning is intractable, the authors identify restrictions ensuring polynomial data complexity. A prototype implements core components in answer set programming (ASP), and an evaluation on a lung cancer use case reports computational feasibility together with positive alignment between inferred events and medical expert opinions. The framework is presented as generic beyond healthcare.

Significance. If the complexity restrictions and repair semantics are rigorously established, the work provides a principled, logic-based method for temporal event detection that could support medical record analysis and generalize to other timestamped domains. Strengths include the explicit separation of rules, constraints, and repair; the use of ASP for implementation; and the falsifiable expert-alignment check in the lung-cancer case. These elements address a practical need for interpretable high-level event inference from raw observations.

major comments (2)

[Complexity analysis section] The central claim that relevant restrictions ensure polynomial-time data complexity is load-bearing for the contribution, yet the manuscript supplies no proof sketch, derivation, or explicit statement of the restrictions (e.g., bounded rule depth, acyclicity conditions, or data-size assumptions). Without this analysis, the tractability result cannot be verified.
[Evaluation section] The lung-cancer evaluation is cited as evidence of both feasibility and expert alignment, but the description contains no quantitative metrics (runtime, number of events inferred, dataset size), error analysis, or comparison against baselines. This weakens the empirical support for the practical interest of the approach.

minor comments (2)

[Introduction / Framework definition] Notation for event existence/termination rules and the repair objective function should be introduced with a small running example early in the paper to improve readability.
[Abstract and Introduction] The abstract and introduction would benefit from a concise statement of the precise restrictions that yield polynomial data complexity, even if the full proof appears later.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback, which highlights key areas for strengthening the manuscript. We address each major comment below, indicating planned revisions to improve clarity, rigor, and empirical detail while preserving the core contribution.

read point-by-point responses

Referee: [Complexity analysis section] The central claim that relevant restrictions ensure polynomial-time data complexity is load-bearing for the contribution, yet the manuscript supplies no proof sketch, derivation, or explicit statement of the restrictions (e.g., bounded rule depth, acyclicity conditions, or data-size assumptions). Without this analysis, the tractability result cannot be verified.

Authors: We agree that the manuscript asserts the existence of restrictions yielding polynomial data complexity but does not supply an explicit characterization or proof sketch. This omission limits verifiability. In the revised version we will add a dedicated subsection that states the precise restrictions (including bounded rule depth, stratification to ensure acyclicity of the dependency graph, and data-size independence from rule size) and provides a concise proof sketch based on standard results for stratified logic programs and bounded treewidth of the event dependency graph. This will make the tractability claim fully verifiable. revision: yes
Referee: [Evaluation section] The lung-cancer evaluation is cited as evidence of both feasibility and expert alignment, but the description contains no quantitative metrics (runtime, number of events inferred, dataset size), error analysis, or comparison against baselines. This weakens the empirical support for the practical interest of the approach.

Authors: The current evaluation section indeed reports only qualitative alignment with expert opinion and omits concrete quantitative metrics. We will expand it to include dataset statistics (number of patient records, total timestamps, and event types), solver runtimes on the ASP encoding, counts of inferred events per patient, and a simple error analysis measuring agreement with the expert annotations. A direct baseline comparison is difficult given the novelty of the combined rule-plus-repair framework, but we will add a discussion of related temporal reasoning systems and explain why quantitative comparison would require new experiments outside the current scope. These additions will provide stronger empirical grounding. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines a logic-based framework using rules for event existence/termination and constraints for incompatibilities, then identifies polynomial-time restrictions on data complexity as an independent theoretical result. The lung-cancer evaluation compares outputs to external medical expert opinions rather than to any fitted parameters or self-referential definitions. No load-bearing step reduces by construction to prior inputs, self-citations, or ansatzes; the derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on standard assumptions from logic programming and temporal reasoning with no new free parameters or invented entities introduced in the abstract.

axioms (2)

domain assumption Logical rules can capture existence and termination conditions for simple temporal events and combine them into meta-events
Core of the framework for event inference from timestamped data.
domain assumption Constraints can identify incompatible combinations of events and a repair mechanism can select preferred consistent sets
Used to handle potentially incorrect inferences in the medical domain.

pith-pipeline@v0.9.0 · 5499 in / 1465 out tokens · 147704 ms · 2026-05-09T21:50:54.367660+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

ACM Comput

Probabilistic complex event recognition: A survey. ACM Comput. Surv.50(5):71:1–71:31. Allen, J. F. 1983. Maintaining knowledge about temporal intervals.Commun. ACM26(11). Apt, K. R.; Blair, H. A.; and Walker, A. 1988. Towards a theory of declarative knowledge. In Minker, J., ed.,Foun- dations of Deductive Databases and Logic Programming. Morgan Kaufmann. ...

work page 1983
[2]

Using ASP(Q) to handle inconsistent prioritized data. InProc. of KR. Bienvenu, M.; Bourgaux, C.; and Goasdou ´e, F. 2014. Querying inconsistent description logic knowledge bases under preferred repair semantics. InProceedings of AAAI. Brandt, S.; Kalayci, E. G.; Ryzhikov, V .; Xiao, G.; and Za- kharyaschev, M. 2018. Querying log data with metric tem- pora...

work page 2014
[3]

telingo = ASP + time. InProc. of LPNMR, 256–269. Cabalar, P. 2022. Temporal ASP: From logical foundations to practical use with telingo. InReasoning Web Tutorial Lectures, volume LNCS 13100. 94–114. Dantsin, E.; Eiter, T.; Gottlob, G.; and V oronkov, A. 2001. Complexity and expressive power of logic programming. ACM Comput. Surv.33(3):374–425. Dwyer, O. P...

work page 2022
[4]

Multi-shot ASP solving with clingo.Theory Pract. Log. Program.19(1):27–82. Hripcsak, G., and Albers, D. J. 2013. Next-generation phe- notyping of electronic health records.J Am Med Inform As- soc20(1):117–121. Hripcsak, G., and Rothschild, A. S. 2005. Agreement, the F-Measure, and Reliability in Information Retrieval.J Am Med Inform Assoc12(3):296–298. Ko...

work page 2013
[5]

Web Semant

Stream reasoning with DatalogMTL.J. Web Semant. 76:100776. Walega, P. A. 2025. Reasoning about time in DatalogMTL: Course notes. InProc. of Reasoning Web Summer School, OASIcs, 9:1–9:23. Wang, D.; Hu, P.; Walega, P. A.; and Grau, B. C. 2022. Me- TeoR: Practical reasoning in datalog with metric temporal operators. InProc. of AAAI. Zhou, L., and Hripcsak, G...

work page 2025
[7]

Guess a subsetS ′ SE ofSE(D,Σ)

work page
[8]

Check ifSandS ′ areΣ-consistent

work page
[9]

In- deed, if an execution returns ‘yes’, then one of (a), (b), or (c) is satisfied

Return ‘yes’ if one of the following conditions holds (else return ‘no’): (a)S ̸=S SE ∪ME(D,S SE,Σ) (b)S SE isnotΣ-consistent, or (c)S ′ SE isΣ-consistent andS SE ⊊S ′ SE We claim that some execution of this non-deterministic pro- cedure returns ‘yes’ iffSisnota consistent timeline. In- deed, if an execution returns ‘yes’, then one of (a), (b), or (c) is ...

work page 2016
[10]

ComputeSE(D,Σ)andS SE =S ∩SE(D,Σ)

work page
[11]

Return ‘no’ if not

Check ifS=S SE ∪ME(D,S SE,Σ). Return ‘no’ if not

work page
[12]

Return ‘no’ if not

Check ifS SE isΣ-consistent. Return ‘no’ if not

work page
[13]

If some setS SE ∪ {σ}isΣ-consistent, return ‘no’, else return ‘yes’

For eachσ∈SE(D,Σ)\ S SE, check ifS SE ∪ {σ}isΣ- consistent. If some setS SE ∪ {σ}isΣ-consistent, return ‘no’, else return ‘yes’. The procedure clearly runs in PTIMEin data complexity and is correct due to the preceding characterization of maximal consistent sets ofSE(D,Σ). Let us now turn to preferred repairs. Using the mono- tonicity property and Definit...

work page
[14]

Return ‘no’ if some consistency check succeeds, else return ‘yes’

For every1≤ℓ≤nand for everyσ ℓ ∈SE(D,Σ) ℓ \ SSE, test whether(S SE)ℓ ∪ {σℓ}isΣ-consistent. Return ‘no’ if some consistency check succeeds, else return ‘yes’. Note that this step remains polynomial-time computable since it involves only polynomially many consistency checks, and each consistency check can be done in PTIME data complexity (cf. proof of Propo...

work page 2016
[15]

Ifℓ=ℓ ′ and[t ′ 1, t′ 2]̸= [t 1, t2], thent 1 ≤t 2 ≤t ′ 1 ≤t ′ 2 or t′ 1 ≤t ′ 2 ≤t 1 ≤t 2

work page
[16]

To show point 1, suppose we haveΠ SE,D |= ℓ R(d,[t 1, t2])andΠ SE,D |= ℓ R(d,[t ′ 1, t′ 2])with[t ′ 1, t′ 2]̸= [t1, t2]

Ifℓ ′ > ℓ, then[t ′ 1, t′ 2]̸= [t 1, t2]and we cannot havet 1 < t′ 1 < t2 ≤t ′ 2 nort ′ 1 ≤t 1 < t ′ 2 < t2 Proof.We give the proof for non-persistent events, the ar- gument for persistent events is similar but simpler. To show point 1, suppose we haveΠ SE,D |= ℓ R(d,[t 1, t2])andΠ SE,D |= ℓ R(d,[t ′ 1, t′ 2])with[t ′ 1, t′ 2]̸= [t1, t2]. We may suppose w...

work page
[17]

We thus aim to show thatt 1 ≤t 2 ≤t ′ 1 ≤t ′

work page
[18]

Assume for a contradiction thatt 1 ≤t ′ 1 < t 2. Ift 1 =t ′ 1, then t2 ̸=t ′ 2 (as we know[t ′ 1, t′ 2]̸= [t 1, t2]), which implies that one of the intervals could have been further extended, vi- olating one of the conditions of Definition 3 (Items 4–5). Thus we havet 1 < t ′ 1 < t 2. However, this also yields a contradiction, since whichever timepoints i...

work page
[19]

However, we must also argue that there is not e ∈T ℓ′ × (R(d))that could block such an extension

Then the timepoints inT ℓ ∃(R(d))which were used to validate item 2 of Definition 3 for[t 1, t2]are also present inT ℓ′ ∃ (R(d)) (sinceℓ ′ > ℓ) and so can be used to show that[t ′ 1, t′ 2]does not verify item 4 (as an earlier start is possible). However, we must also argue that there is not e ∈T ℓ′ × (R(d))that could block such an extension. It is here th...

work page
[20]

malignant neoplasm of bronchus and lung

The right boundary is chosen as the maximal sucht ′ 2. 2.Termination-aware expansion.If a termination time- pointt b ∈T ℓ ×(R(d))satisfies t2 < t b ≤t 2 +w, the interval is closed att b. The earliest compatible termi- nation is selected. 3.Lower-priority levels.After processing the highest- priority level, the procedure continues with lower- confidence le...

work page 2005

[1] [1]

ACM Comput

Probabilistic complex event recognition: A survey. ACM Comput. Surv.50(5):71:1–71:31. Allen, J. F. 1983. Maintaining knowledge about temporal intervals.Commun. ACM26(11). Apt, K. R.; Blair, H. A.; and Walker, A. 1988. Towards a theory of declarative knowledge. In Minker, J., ed.,Foun- dations of Deductive Databases and Logic Programming. Morgan Kaufmann. ...

work page 1983

[2] [2]

Using ASP(Q) to handle inconsistent prioritized data. InProc. of KR. Bienvenu, M.; Bourgaux, C.; and Goasdou ´e, F. 2014. Querying inconsistent description logic knowledge bases under preferred repair semantics. InProceedings of AAAI. Brandt, S.; Kalayci, E. G.; Ryzhikov, V .; Xiao, G.; and Za- kharyaschev, M. 2018. Querying log data with metric tem- pora...

work page 2014

[3] [3]

telingo = ASP + time. InProc. of LPNMR, 256–269. Cabalar, P. 2022. Temporal ASP: From logical foundations to practical use with telingo. InReasoning Web Tutorial Lectures, volume LNCS 13100. 94–114. Dantsin, E.; Eiter, T.; Gottlob, G.; and V oronkov, A. 2001. Complexity and expressive power of logic programming. ACM Comput. Surv.33(3):374–425. Dwyer, O. P...

work page 2022

[4] [4]

Multi-shot ASP solving with clingo.Theory Pract. Log. Program.19(1):27–82. Hripcsak, G., and Albers, D. J. 2013. Next-generation phe- notyping of electronic health records.J Am Med Inform As- soc20(1):117–121. Hripcsak, G., and Rothschild, A. S. 2005. Agreement, the F-Measure, and Reliability in Information Retrieval.J Am Med Inform Assoc12(3):296–298. Ko...

work page 2013

[5] [5]

Web Semant

Stream reasoning with DatalogMTL.J. Web Semant. 76:100776. Walega, P. A. 2025. Reasoning about time in DatalogMTL: Course notes. InProc. of Reasoning Web Summer School, OASIcs, 9:1–9:23. Wang, D.; Hu, P.; Walega, P. A.; and Grau, B. C. 2022. Me- TeoR: Practical reasoning in datalog with metric temporal operators. InProc. of AAAI. Zhou, L., and Hripcsak, G...

work page 2025

[6] [7]

Guess a subsetS ′ SE ofSE(D,Σ)

work page

[7] [8]

Check ifSandS ′ areΣ-consistent

work page

[8] [9]

In- deed, if an execution returns ‘yes’, then one of (a), (b), or (c) is satisfied

Return ‘yes’ if one of the following conditions holds (else return ‘no’): (a)S ̸=S SE ∪ME(D,S SE,Σ) (b)S SE isnotΣ-consistent, or (c)S ′ SE isΣ-consistent andS SE ⊊S ′ SE We claim that some execution of this non-deterministic pro- cedure returns ‘yes’ iffSisnota consistent timeline. In- deed, if an execution returns ‘yes’, then one of (a), (b), or (c) is ...

work page 2016

[9] [10]

ComputeSE(D,Σ)andS SE =S ∩SE(D,Σ)

work page

[10] [11]

Return ‘no’ if not

Check ifS=S SE ∪ME(D,S SE,Σ). Return ‘no’ if not

work page

[11] [12]

Return ‘no’ if not

Check ifS SE isΣ-consistent. Return ‘no’ if not

work page

[12] [13]

If some setS SE ∪ {σ}isΣ-consistent, return ‘no’, else return ‘yes’

For eachσ∈SE(D,Σ)\ S SE, check ifS SE ∪ {σ}isΣ- consistent. If some setS SE ∪ {σ}isΣ-consistent, return ‘no’, else return ‘yes’. The procedure clearly runs in PTIMEin data complexity and is correct due to the preceding characterization of maximal consistent sets ofSE(D,Σ). Let us now turn to preferred repairs. Using the mono- tonicity property and Definit...

work page

[13] [14]

Return ‘no’ if some consistency check succeeds, else return ‘yes’

For every1≤ℓ≤nand for everyσ ℓ ∈SE(D,Σ) ℓ \ SSE, test whether(S SE)ℓ ∪ {σℓ}isΣ-consistent. Return ‘no’ if some consistency check succeeds, else return ‘yes’. Note that this step remains polynomial-time computable since it involves only polynomially many consistency checks, and each consistency check can be done in PTIME data complexity (cf. proof of Propo...

work page 2016

[14] [15]

Ifℓ=ℓ ′ and[t ′ 1, t′ 2]̸= [t 1, t2], thent 1 ≤t 2 ≤t ′ 1 ≤t ′ 2 or t′ 1 ≤t ′ 2 ≤t 1 ≤t 2

work page

[15] [16]

To show point 1, suppose we haveΠ SE,D |= ℓ R(d,[t 1, t2])andΠ SE,D |= ℓ R(d,[t ′ 1, t′ 2])with[t ′ 1, t′ 2]̸= [t1, t2]

Ifℓ ′ > ℓ, then[t ′ 1, t′ 2]̸= [t 1, t2]and we cannot havet 1 < t′ 1 < t2 ≤t ′ 2 nort ′ 1 ≤t 1 < t ′ 2 < t2 Proof.We give the proof for non-persistent events, the ar- gument for persistent events is similar but simpler. To show point 1, suppose we haveΠ SE,D |= ℓ R(d,[t 1, t2])andΠ SE,D |= ℓ R(d,[t ′ 1, t′ 2])with[t ′ 1, t′ 2]̸= [t1, t2]. We may suppose w...

work page

[16] [17]

We thus aim to show thatt 1 ≤t 2 ≤t ′ 1 ≤t ′

work page

[17] [18]

Assume for a contradiction thatt 1 ≤t ′ 1 < t 2. Ift 1 =t ′ 1, then t2 ̸=t ′ 2 (as we know[t ′ 1, t′ 2]̸= [t 1, t2]), which implies that one of the intervals could have been further extended, vi- olating one of the conditions of Definition 3 (Items 4–5). Thus we havet 1 < t ′ 1 < t 2. However, this also yields a contradiction, since whichever timepoints i...

work page

[18] [19]

However, we must also argue that there is not e ∈T ℓ′ × (R(d))that could block such an extension

Then the timepoints inT ℓ ∃(R(d))which were used to validate item 2 of Definition 3 for[t 1, t2]are also present inT ℓ′ ∃ (R(d)) (sinceℓ ′ > ℓ) and so can be used to show that[t ′ 1, t′ 2]does not verify item 4 (as an earlier start is possible). However, we must also argue that there is not e ∈T ℓ′ × (R(d))that could block such an extension. It is here th...

work page

[19] [20]

malignant neoplasm of bronchus and lung

The right boundary is chosen as the maximal sucht ′ 2. 2.Termination-aware expansion.If a termination time- pointt b ∈T ℓ ×(R(d))satisfies t2 < t b ≤t 2 +w, the interval is closed att b. The earliest compatible termi- nation is selected. 3.Lower-priority levels.After processing the highest- priority level, the procedure continues with lower- confidence le...

work page 2005