{"id":"dac8ea80-7c24-4622-abf9-ac9a5122b216","arxiv_id":"2607.15223","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"DTL is a new probabilistic temporal logic expressing conditional-independence hyperproperties, with a PTIME linear fragment and an automata-theoretic qualitative fragment.","lead":"The paper introduces DTL, a logic for probabilistic hyperproperties that conditions on finite or infinite event histories using measure disintegration. It proves the full logic's model checking is undecidable and identifies two decidable fragments: a linear fragment with polynomial-time model checking and a qualitative fragment decidable for cascade-compatible systems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Undecidability reduction in Theorem 14 evaluates the DTL formula at timestamp 0 only, so it does not encode PFA strict cutpoint emptiness.","rationale":"The reader's weakest_assumption about the qualitative fragment's cascade property and precise labeling is a legitimate concern about assumption disclosure and proof density, but Theorem 20 explicitly states those hypotheses, so it is a conditional result that can in principle be checked. The undecidability proof in Theorem 14 is a stated central claim whose formula, under the paper's own semantics, does not express the intended PFA condition; this is a concrete, checkable flaw. A one-state instantiation proves the reduction's claimed equivalence fails. This does not necessarily invalidate the decidable-fragment results, but it means the paper's scope claim ('full DTL model checking is undecidable') is not established as written and the proof needs correction. Hence conditional acceptance is appropriate: the paper should be revised to fix the reduction (likely by adding an appropriate temporal operator) and to clarify the qualitative-fragment assumptions.","tokens_in":27295,"tokens_out":27237,"duration_ms":218627,"concrete_test":"Instantiate the Theorem 14 reduction with d=1, G={[1]}, π=[1], f=[0]. The PFA is empty above 1/2 because every acceptance probability is 0. But the DTL formula as written evaluates to true: at timestamp 0, P(af|[AP]) is the unconditional probability that a_f holds at step 0, which is 1, so the outer P>0 is satisfied. This demonstrates that the reduction does not encode strict cutpoint emptiness. If the authors intended a missing `F` (eventually) operator, the counterexample also shows the formula must be revised.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing concern is that the undecidability proof (Theorem 14) fails as written. The formula is ϕ := P( (P(af|[AP]) > 0.5) ) > 0. Under the closed-formula semantics of §3.2.2, this is evaluated at timestamp n=0 and the initial cut C0(p)=0. The inner probabilistic operator updates the cut to C'(p)=max(C0(p),0)=0 for all p∈AP, so L(C') is a singleton; thus P(af|[AP]) is the unconditional probability of a_f at step 0, a constant independent of the trace. The proof nevertheless argues that conditioning on an AP-prefix t of length m fixes t(0)..t(m−1) and evolves the internal distribution as π^T η(t(0))···η(t(m−1)) f. That would require evaluating the inner operator at timestamp m, but no temporal operator (such as F or an iterated next) is present to advance the timestamp. Consequently, the formula's truth is determined by the step-0 marginal, not by existence of a finite word of matrices, so the claimed equivalence with PFA strict cutpoint emptiness does not hold. A concrete one-state instance (d=1, G={[1]}, π=[1], f=[0]) gives an empty PFA yet a true formula, since a_f has probability 1 at step 0.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Disintegration Temporal Logic (DTL), a probabilistic temporal logic with a conditioning operator based on measure disintegration. DTL is designed to express probabilistic hyperproperties such as probabilistic non-interference, perfect indistinguishability, and properties of systems interacting with stochastic environments. The authors claim that model checking Markov chains against full DTL is undecidable (Theorem 14), that the linear fragment admits a polynomial-time model-checking algorithm (Theorem 18), and that the qualitative fragment is decidable for cascade-compatible, precisely labeled Markov chains with a non-elementary upper bound (Theorem 20). The technical development includes a measurability theorem for the semantics (Theorem 13), a constructive disintegration theorem (Theorem 5), and an automata-theoretic construction for the qualitative fragment.","tokens_in":27562,"tokens_out":17308,"duration_ms":132291,"significance":"If the technical results stand, DTL is a novel and well-motivated framework for conditional-independence hyperproperties, with a genuinely useful PTIME algorithm for the linear fragment and a nontrivial automata-theoretic decision procedure for a qualitative fragment. The measure-theoretic foundation, especially the measurability and a.e.-uniqueness theorem (Theorem 13), is careful and necessary. However, the undecidability proof is flawed as written, and the qualitative-fragment decidability claim is substantially narrower than the abstract suggests because it requires cascade-compatibility and precise labeling.","major_comments":[{"comment":"The reduction is invalid as written. The formula ϕ := P( (P(af|[AP])>0.5) ) > 0 evaluates the inner probabilistic operator at timestamp n=0 under the semantics of §3.2.2; the outer P does not advance the timestamp, and C0(p)=0 makes the inner conditioning empty. Thus the inner value is the step-0 marginal of af, not the prefix-dependent probability. A one-state PFA with d=1, G={[1]}, π=[1], f=[0] is empty, yet the constructed Markov chain satisfies the formula because af holds with probability 1 at step 0. The correctness argument requires evaluating the inner operator at timestamp m (e.g., via F or an iterated next). This is load-bearing for the undecidability claim.","section":"§3.2.2, Theorem 14"},{"comment":"The production for θ is printed as 'θ ::= P(κ|[A1]) = P(κ|[A2]) | θ | θ | P(θ|[B]) = 1', with two bare θ alternatives; the connective symbols are missing, so the fragment is not well-defined. Moreover, the proof of Theorem 18 assumes θ is a chain of next operators and P(...)=1 operators around the atomic equality; it does not explain how Boolean combinations inside θ are treated. Please restore the full grammar and adjust the algorithm/proof accordingly, or state the intended fragment precisely.","section":"§5, linear fragment grammar"},{"comment":"The abstract and introduction present the qualitative-fragment result without the hypotheses of Theorem 20: the Markov chain must be precisely labeled and the formula cascade-compatible. Corollary 23 and Lemma 25 rely on the cascade property for the finite-step stabilization, and on injective labeling to identify paths by their label. Without these assumptions the algorithm has no correctness guarantee. The scope should be disclosed in the abstract, or the theorem generalized if possible.","section":"Abstract / §6, Theorem 20"}],"minor_comments":[{"comment":"The sentence 's_X denotes the projection of s on Y' should read 'on X'.","section":"§2.1"},{"comment":"In the labeling definition, 'iff j = 1' should be 'if f_j = 1' (or the intended condition clarified).","section":"Theorem 14 proof"},{"comment":"The inequality 'C(a) ≤ N for all a ∈ AP′' should probably be 'a ∈ AP\\AP′'.","section":"Definition 21"},{"comment":"The encoding of finite timestamps and cuts via traces of the form 0^n ⊥ ... is under-specified; define the decoding from {0,⊥,⊤}-traces to N∪{ω} explicitly.","section":"§6.2"},{"comment":"The complexity bound PTIME(|D|·n) is inconsistent with the vector-space dimension |Q|·n^2 used in the stabilization argument; the bound should be polynomial in |Q|·n^2 (still PTIME).","section":"§5, Lemma 17"},{"comment":"The proof uses 'µ-a.e. T' for individual n; the conclusion for all n relies on a countable union of null sets. This is acceptable but should be stated explicitly.","section":"§6.3, Lemma 25"}],"recommendation":"major_revision","confidential_remarks":"The undecidability proof is the main obstacle. If the authors replace the formula with one containing an F (or otherwise advance the timestamp), the reduction may go through, but the current proof does not establish the theorem. The linear-fragment grammar must also be fixed, and the abstract should be honest about the cascade-compatibility and precise-labeling restrictions. I see no grounds for rejection if these issues are repaired, but the revision needs to be substantive."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: the disintegration semantics is real and worth a look. The paper builds a probabilistic hyperproperty logic around conditioning on finite or infinite observation sequences via measure-theoretic disintegration, which is new. The linear fragment (conditional-independence properties) has a PTIME model-checking algorithm via \"multidynamic automata,\" and the qualitative fragment reuses alternating-automata and BSCC machinery. The expressiveness story—Gray's PNI, perfect indistinguishability, stochastic environments—is well done.\n\nSecond thing: the undecidability proof, as printed, doesn't go through. The formula is P( (P(af|[AP])>0.5) )>0. At timestamp 0 the inner P(af|[AP]) updates the cut by max(0,0)=0, so L(C') is a singleton; it conditions on the empty prefix and just measures af at the first step. The proof talks about conditioning on an observation of length m and the distribution evolving as pi^T eta(t(0))...; that would require a temporal operator (F, or an iterated next) to advance the timestamp, and there isn't one. The stress-test's concrete one-state counterexample is off—with d=1, f=[0], af is never true—but the structural point is right: the reduction as written checks only the initial marginal, not existence of a finite matrix word. If a \"finally\" was lost in typesetting, the reduction is likely fixable, but the manuscript doesn't say that.\n\nThe qualitative fragment result is also softer than the abstract suggests. Theorem 20 applies only to cascade-compatible, precisely labeled chains. The cascade property is a conditional-independence condition, and Corollary 23 uses it to make the Theorem 5 limit stabilize after finitely many steps. Without that, Lemma 25 doesn't work. The abstract doesn't disclose these restrictions. This matters for anyone applying the algorithm.\n\nMinor stuff: the theta grammar is missing connective symbols; the proof of Lemma 25 is sketchy around measure-zero sets; no formal verification. None of this is fatal to the linear-fragment story.\n\nVerdict: serious paper, worth a real referee. The disintegration semantics and PTIME linear fragment are genuine contributions. But the undecidability theorem needs repair and the qualitative fragment needs honest assumption disclosure. I'd send to review with clear requests.","headline":"New disintegration-based probabilistic hyperproperty logic with a genuinely useful linear fragment, but the undecidability proof as printed fails and the qualitative fragment is oversold.","tokens_in":28092,"tokens_out":7663,"would_cite":true,"duration_ms":62426,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03B70","68Q60","60A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Disintegration Temporal Logic conditions probabilities on finite or infinite event sequences, making probabilistic hyperproperties like general non-interference expressible and, in two fragments, decidable.","keywords":["Disintegration Temporal Logic","probabilistic hyperproperties","probabilistic non-interference","perfect indistinguishability","measure disintegration","Markov chain model checking","undecidability","automata-theoretic verification"],"falsifier":"Construct a small Markov chain where the future of a proposition b at step 2 depends on the full first-step prefix of another proposition a, not just on the b-projection, so the cascade property fails. Evaluate a qualitative formula such as P(φ | [{b}]) = 1, where φ asserts b at step 2, and compare the algorithm's output with the conditional probability computed as the limit of finite-prefix conditioning per Theorem 5; a mismatch would show the cascade assumption is load-bearing.","tokens_in":27121,"feed_emoji":"🎲","tokens_out":6565,"duration_ms":55785,"temperature":0.7,"pith_summary":"This paper introduces Disintegration Temporal Logic (DTL), a probabilistic temporal logic that conditions probabilities on finite or infinite sequences of events through measure disintegration. Because disintegration handles probability-zero events, DTL can condition on individual infinite traces, which lets it express probabilistic hyperproperties that earlier logics could not capture, including general probabilistic non-interference and perfect indistinguishability. The paper shows that full DTL model checking is undecidable, but the linear fragment, which contains those security properties, is decidable in polynomial time. It also shows that the qualitative fragment, where inner probabilities compare only to 0 or 1, is decidable for precisely labeled Markov chains satisfying the cascade property, with complexity a tower of exponentials in alternation depth. The framework can distinguish systems that have the same overall failure probability but spread failures differently across environment executions.","feed_headline":"Disintegration logic verifies probabilistic hyperproperties","feed_subtitle":"Full DTL is undecidable, yet a linear fragment checks general non-interference in polynomial time.","key_machinery":"The central object is a cut—a function assigning each atomic proposition either a finite length or the symbol ω—splitting a trace into a conditioned prefix L(C) and an unconstrained suffix U(C). Disintegration kernels give conditional distributions of the suffix given the prefix even for probability-zero events, with Theorem 5 showing the kernel is a limit of finite-prefix conditionings. The cascade property, a conditional-independence condition, makes that limit stabilize after finitely many steps and drives the qualitative-fragment algorithm. The linear-fragment algorithm instead reduces conditional-probability equality to a quadratic form over a multidynamic automaton, using pointwise mod","core_discovery":"DTL evaluates formulas against a trace, a timestamp, a cut, and a probability measure. A cut divides each trace into a conditioned prefix and an unconstrained suffix, and disintegration yields the conditional distribution of the future given the prefix, even when the prefix has probability zero. The semantics are independent of the chosen disintegration kernel up to measure zero. The paper's main algorithmic contributions are two decidable fragments: the linear fragment, where probabilities are compared for equality or against 1, has a polynomial-time model-checking procedure via reduction to a quadratic form over paths of a multidynamic automaton; the qualitative fragment, where inner proba","pith_inferences":["A practical implementation could first run the polynomial-time cascade-compatibility check and then apply the qualitative algorithm, rejecting inapplicable inputs before verification; this workflow is implied but not explicitly stated.","The linear-fragment quadratic-form reduction could plausibly be extended from exact equality to approximate or quantitative conditional-independence checking, yielding a broader set of tools for information-flow measurement.","The soft scheduler quantification suggests a more general pattern: probabilistic systems whose schedulers are drawn from a product measure may admit decidable hyperproperty verification in cases where strict existential quantification is undecidable, though that generalization remains unproven.","The framework's failure-concentration distinction could support a testable robustness metric: compute the maximum, over positive-measure environment traces, of the conditional probability of an undesirable behavior, which DTL can express but classical average-based logics cannot."],"forward_implications":["General probabilistic non-interference and perfect indistinguishability are expressible as DTL formulas and model-checkable in polynomial time, something earlier probabilistic temporal logics could not do.","Any extension that retains full conditional-probability operators must respect the linear or qualitative fragment boundaries if it wants decidability.","The qualitative fragment provides a decidable soft alternative to existential scheduler quantification: instead of asking whether some scheduler achieves a goal, it asks whether a positive-measure set of schedulers does, turning undecidable probabilistic-automata problems into decidable ones.","DTL can separate systems with identical average failure probability according to how failures are distributed over environment executions, revealing concentrated failures that average-based reasoning misses.","Because the cascade property is expressible in the linear fragment, whether a chain qualifies for the qualitative algorithm can itself be checked in polynomial time."],"fun_headline_variants":["Polynomial-time check for probabilistic non-interference via DTL","Linear DTL fragment verifies probabilistic hyperproperties in P","Undecidable DTL still has tractable fragments for hyperproperties","Disintegration logic: decidable sublogics for probabilistic properties","Even full DTL's undecidability can't hide all hyperproperties"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The qualitative-fragment decidability theorem requires the Markov chain's induced distribution to satisfy the cascade property—once a prefix is fixed, the future of the conditioned propositions must not depend on the rest of the prefix—and the chain must be precisely labeled; the correctness proof collapses if an arbitrary chain is fed to the algorithm.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time check for probabilistic non-interference via DTL","Linear DTL fragment verifies probabilistic hyperproperties in P","Undecidable DTL still has tractable fragments for hyperproperties","Disintegration logic: decidable sublogics for probabilistic properties","Even full DTL's undecidability can't hide all hyperproperties"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000445,"raw_usage":{"total_tokens":2072,"prompt_tokens":711,"completion_tokens":1361,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":455,"completion_tokens_details":{"reasoning_tokens":1272}},"tokens_in":455,"tokens_out":1361,"duration_ms":9496,"temperature":1.0,"reasoning_tokens":1272,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T23:48:32.429055+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small Markov chain where the future of a proposition b at step 2 depends on the full first-step prefix of another proposition a, not just on the b-projection, so the cascade property fails. Evaluate a qualitative formula such as P(φ | [{b}]) = 1, where φ asserts b at step 2, and compare the algorithm's output with the conditional probability computed as the limit of finite-prefix conditioning per Theorem 5; a mismatch would show the cascade assumption is load-bearing.","supporting_citations":[],"review_version":1}