{"id":"7c97fff3-19a2-482e-be5f-f5b163aac3c6","arxiv_id":"2608.06689","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Upper and lower sparse abstractions of monotone control systems form a complete pair: the upper one admits controller refinement and the lower one certifies controller absence, in both model-based and data-driven settings.","lead":"This paper introduces a new behavioral relation and two finite abstractions for monotone control systems that together certify both when a controller exists and when it cannot exist. The results extend to abstractions built directly from sampled data, with a tunable trade-off between accuracy and discretization size.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Data-driven Theorems 4 and 5 implicitly require Assumption 4 (monotone partition) for the max/min in (18) and (21) to be well-defined; the theorems state only Assumption 3, so a non-monotone partition can make the data-driven abstractions undefined.","rationale":"The paper's model-based core is sound: Theorem 2's bracketing UΣ ≼ SΣ ≼ LΣ follows from monotonicity and lower closedness, and Theorem 3's conservativeness bound uses Assumption 4 explicitly. The data-driven extension, however, has a real unstated hypothesis. The definitions of ΔUD and ΔLD in (18) and (21) rely on choosing a cell with extremal upper or lower bound among cells intersecting a down-set or up-set. Without Assumption 4, there can be two intersecting cells whose bounds are incomparable, so the required extremum does not exist. The example with cells A=[0,1]×[0,2], B=[1,2]×[0,1], C=[1,2]×[1,2] and Qu=↓(1.5,0.5) makes this concrete: the candidate cells have upper bounds (1,2) and (2,1), and no cell has upper bound (2,2), so (18) is undefined. Assumption 4(ii) would force the upper bound of the cell containing the extremal data point to dominate all intersecting cells; Assumption 4(i) plays the analogous role for the lower-sparse case. Because Theorems 4 and 5 are stated under Assumption 3 only, this is a genuine missing hypothesis, not merely a proof gap. The reader's verdict of CONDITIONAL is therefore appropriate: the identified issue is local to the data-driven theorems, is easily fixed by adding Assumption 4, and does not undermine the model-based claims. No additional concern about the model-based results was found that would change the verdict.","tokens_in":27266,"tokens_out":40169,"duration_ms":392673,"concrete_test":"Take X=[0,2]^2 with the three-cell partition A=[0,1]×[0,2], B=[1,2]×[0,1], C=[1,2]×[1,2], and use the single data point ((2,2), u, (1.5,0.5)) in K. For q=C and input u, K+(q,u) is nonempty and Qu(q,u)=↓(1.5,0.5). Compute the right-hand side of (18): the cells intersecting Qu are A and B, with upper bounds (1,2) and (2,1); the componentwise maximum (2,2) is not the upper bound of any intersecting cell, so no q' satisfies (18). Reproducing this computation shows that the data-driven upper abstraction is undefined for a partition satisfying Assumption 3 but not Assumption 4, confirming the missing hypothesis in Theorems 4 and 5.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's concern is essentially correct, and it is the load-bearing issue in the data-driven half of the paper. Theorems 4 and 5 are stated under Assumption 3 only, but the transition definitions (18) and (21) require selecting the cell whose upper bound (respectively lower bound) is the componentwise extremum over all cells intersecting a down-set or up-set. For an arbitrary rectangular partition this extremum need not be attained. Example: X=[0,2]^2 partitioned into A=[0,1]×[0,2], B=[1,2]×[0,1], C=[1,2]×[1,2] violates Assumption 4(ii): x=(0.5,0.5)≤x'=(1.5,0.5) but the quantizer upper bounds satisfy (1,2)≰(2,1). If the data produce Qu=↓(1.5,0.5), both A and B intersect Qu, with upper bounds (1,2) and (2,1); their componentwise maximum (2,2) is not the upper bound of any cell intersecting Qu, so equation (18) has no solution and UΣD is undefined. Assumption 4(i)-(ii) is exactly what ensures that the cell containing the extremal data point dominates all intersecting cells, making the max/min in (18) and (21) well-defined and validating the proof steps x^{q'_1}_1≤x^{q'_2}_1 and x^{q'_1}_2≤x^{q'_2}_2. Since Section V never states this hypothesis, Theorems 4 and 5 are missing a necessary assumption. The model-based Theorem 2 and the conservativeness Theorem 3 are not affected; the gap is repairable by adding Assumption 4 to the data-driven statements and proofs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a new behavioral relation, approximate strong upper alternating simulation (ASUAS), which replaces the usual output-closeness condition with an output-ordering condition. Building on ASUAS, the authors construct upper- and lower-sparse abstractions UΣ and LΣ for discrete-time monotone control systems and prove the bracketing UΣ ≼^0_u SΣ ≼^0_u LΣ, so that a controller for UΣ refines to SΣ and absence of a controller for LΣ certifies absence for SΣ. Theorem 3 shows that the gap between the two abstractions can be controlled by the space-discretization parameter η through the Jacobian bound ε_i ≥ ∑_j α_ij η_j. Section V extends the construction to a data-driven setting, where abstractions UΣD, LΣD are built from a finite dataset of transitions sampled under the maximum disturbance; Theorem 4 claims UΣD ≼^0_u UΣ ≼^0_u SΣ ≼^0_u LΣ ≼^0_u LΣD, and Theorem 5 adds a conservativeness bound with a probabilistic version in Proposition 2. The theoretical results are illustrated on an adaptive cruise control example.","tokens_in":27751,"tokens_out":21543,"duration_ms":193749,"significance":"If the claims hold, the paper makes a significant contribution to symbolic control: it provides the first complete abstraction pair for monotone systems that does not require incremental stability, and it does so with a constructive way to tune the abstraction gap. The model-based part (Theorems 2 and 3) appears sound, and the proofs are genuinely theorem-based: the Jacobian bounds αij and the sampling interval ξ are user-provided, not fitted to the numerical results. The data-driven extension addresses a practically important problem, and the PAC-style sample bound in Proposition 2 is supported by a Monte Carlo validation. The main flaw is that the data-driven Theorems 4 and 5 miss a necessary monotone-partition hypothesis in their statements, which makes this half of the paper incomplete as written. The issue is repairable without changing the overall approach.","major_comments":[{"comment":"The data-driven theorems are stated under Assumption 3 only, but their proofs require the monotone-partition property of Assumption 4. The transition definitions (18) and (21) require that the sets of upper bounds, respectively lower bounds, of cells intersecting the down-set Qu(q,u) and the up-set Ql(q,u) have a componentwise maximum, respectively minimum, that is attained by one of the intersecting cells. Assumption 3 does not guarantee this. For example, with X=[0,2]^2 partitioned into A=[0,1]×[0,2], B=[1,2]×[0,1], C=[1,2]×[1,2], and Qu=↓(1.5,0.5), the cells A and B intersect Qu and have upper bounds (1,2) and (2,1), whose componentwise maximum (2,2) is not the upper bound of any cell intersecting Qu, so (18) has no solution. Assumption 4(i)-(ii) is exactly the condition that makes such extrema well-defined and validates the proof steps that compare x^{q'_1}_1 with x^{q'_2}_1 and x^{q'_1}_2 with x^{q'_2}_2. I recommend adding Assumption 4 to the hypotheses of Theorems 4 and 5 and to the definitions of UΣD and LΣD, and explicitly invoking it in the proofs.","section":"Section V, Theorems 4 and 5, Eqs. (18) and (21)"},{"comment":"The proof states that for u2 ∈ U_a^L(q2), the point max{f(x^{q2}_1,u2,d^m_2)+Ωε(0)} belongs to X. This is not generally true: since X is only lower closed, the ε-ball around a point of X can extend outside X in the upward direction. The subsequent inclusion ↓max{...} ⊆ ↓X ⊆ X may therefore fail. The conclusion that u1 ∈ U_a^U(q1) can be obtained more directly, because the transition relation of the upper-sparse abstraction only needs the point f(x^{q1}_2,u1,d^m_2) to lie in X, which follows from f mapping X into X and the partition covering X. The proof should be revised to avoid the unproved claim that the maximum of the disturbed ball is in X, or an explicit assumption ensuring that the ball remains in X should be added.","section":"Section IV-B, proof of Theorem 3, Eq. (14)"}],"minor_comments":[{"comment":"The notation min/max for sets of vectors is used ambiguously. For instance, x^{q'}_2 = max{x^{q⋆}_2 | q⋆ ∩ Qu(q,u) ≠ ∅} selects the componentwise maximum of a set of vectors; this is well-defined only when the set has a greatest element, which is precisely the issue raised in the major comment. The paper should define the intended arg-extremum notation and state the conditions under which it exists.","section":"Section V-A, Eqs. (18) and (21)"},{"comment":"The text says the second inequality in (26) comes from 'equation (5)' and Lemma 1, but there is no equation (5); the intended reference is the bound ε_i ≥ ∑_j α_ij ξ_j together with Lemma 1.","section":"Section V-B, Eq. (26)"},{"comment":"The data-driven construction at the start of Section V assumes that D is a single interval [D, D] so that the 'maximum disturbance' is well-defined, but Theorem 4 states Assumption 1, which allows finite unions of intervals. The theorem statement should explicitly restrict to the single-interval case or explain how the maximum disturbance is selected in the union case.","section":"Section V-A, Theorem 4"},{"comment":"Assumption 6 refers to sampling from intervals I^+_q(ξ), which may lie outside X; the text mentions an extended set tilde X but Theorem 5 as stated does not refer to tilde X. The statement should make explicit that data points are drawn from an extended state set tilde X with X ⊆ tilde X and I^+_q(ξ) ⊆ tilde X, and that the data-driven abstraction is defined on the appropriate state set.","section":"Section V-B, Theorem 5 and Assumption 6"},{"comment":"The footnote says overlaps of measure zero are ignored 'as is done in [8]', but since the proofs rely on partition cells covering X and on the quantizer being well-defined, the treatment of overlapping boundaries should be stated more carefully, for instance by assigning boundary points to exactly one cell.","section":"Section IV-A, footnote 3"}],"recommendation":"major_revision","confidential_remarks":"The reader's concern about the missing Assumption 4 in the data-driven theorems is correct and is the main obstacle to acceptance. The model-based results appear sound, and the repair is local: add the assumption to the statements and proofs of Theorems 4 and 5. The paper fits the scope of the journal and the numerical validation, including the Monte Carlo check of Proposition 2, is a strength. I would encourage the authors to also re-examine the proof of Theorem 3 regarding the maximum of the disturbed ball, although there is an obvious fix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Plainly: the model-based half of this paper is good and genuinely new; the data-driven half as stated is not fully proven. Theorems 4 and 5 are missing a hypothesis the proofs need.\n\nThe new thing here is the complete abstraction pair: an upper-sparse abstraction that is sufficient and a lower-sparse abstraction that is necessary, joined by a new ASUAS relation which replaces output closeness with output ordering. That is a real step beyond the sound-only abstractions for monotone systems, and it gives a practical way to certify controller absence. Theorem 2 is proved cleanly under the stated assumptions. Theorem 3, which tunes the conservativeness gap through the discretization parameter, also checks out. The numerical experiments are honest: they illustrate the bracketing and do not calibrate anything. No circularity; the αij and ξ are user-specified bounds, not fit to results.\n\nThe soft spot is in Section V. Theorems 4 and 5 are stated under Assumption 3, but the transition definitions (18) and (21) require a componentwise extremum over all cells intersecting a down-set or up-set, and for an arbitrary rectangular partition that extremum may not be attained by any cell's bound. A partition like [0,2]^2 split into A=[0,1]×[0,2], B=[1,2]×[0,1], C=[1,2]×[1,2] violates Assumption 4, and a down-set can intersect two cells with incomparable upper bounds, leaving the max in (18) undefined. Assumption 4—monotonicity of the partition—is exactly what makes the cell containing the extremal data point dominate all intersecting cells, and the proofs of Theorems 4 and 5 use that implicitly when they assert x^{q'_1}_1 ≤ x^{q'_2}_1. Section V never states Assumption 4. This is repairable: add Assumption 4 to the hypotheses and reference it explicitly in the proofs. There is also a minor wording issue: the paper promises unicity of the successor in (18), but unless the partition is monotone there is not even existence, and even with Assumption 4 you get determinism only after choosing the extremal cell, not uniqueness of the cell itself.\n\nThe model-based core holds up, so this deserves a serious referee. The right outcome is conditional: accept after fixing the data-driven assumptions. The paper will be useful to symbolic control and monotone systems people, and the complete abstraction pair is worth citing even before the data-driven half is patched.","headline":"Model-based complete abstractions are solid and new; the data-driven theorems need an additional monotone-partition hypothesis before they are true as stated.","tokens_in":28260,"tokens_out":2537,"would_cite":true,"duration_ms":24033,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93C55","68Q60","93C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"For a monotone control system, a pair of coarse models can bracket the exact controllability of the original system.","keywords":["monotone control systems","alternating simulation","symbolic control","complete abstractions","data-driven abstraction","formal verification","transition systems","safety synthesis"],"falsifier":"Run the data-driven construction on a monotone system using a non-monotone partition, for example two adjacent cells with ordered upper corners but crossed lower corners as in the third partition of Figure 3, and check whether $U_{\\Sigma_D} \\preceq^0_u U_\\Sigma$ still holds; a single transition where the data-driven successor jumps above or below the model-based successor would refute Theorem 4 as stated.","tokens_in":27060,"feed_emoji":"🎛️","tokens_out":4842,"duration_ms":40520,"temperature":0.7,"pith_summary":"This paper introduces a behavioral relation called approximate strong upper alternating simulation (ASUAS), an order-based notion of simulation tailored to monotone control systems. Using it, the authors build two finite abstractions of a discrete-time monotone system, an upper-sparse and a lower-sparse abstraction, and prove that they bracket the original system in the ASUAS order. The practical payoff is two-sided: a controller synthesized for the upper abstraction refines into a controller for the original, and if no controller exists for the lower abstraction, then no controller exists for the original. The same bracketing is rederived when the abstractions are built directly from finite sampled data rather than from the model. A tunable discretization parameter provably controls the conservativeness gap between the two abstractions, so the method yields a complete abstraction pair for this class of systems.","feed_headline":"Two coarse models bracket monotone control systems","feed_subtitle":"Any controller for the upper model refines to the real system; if the lower model has no controller, neither does the real system.","key_machinery":"The central object is the $\\varepsilon$-approximate strong upper alternating simulation (ASUAS), a relation $R$ between concrete and abstract states requiring $H_1(x_1) \\leq H_2(x_2)+\\varepsilon$ and, for every abstract input $u_2$, enabling every concrete input $u_1 \\leq u_2$ with matching successors. This order-only condition, instead of distance-based closeness, is what makes monotone systems amenable to exact bracketing. The upper-sparse abstraction keeps the upper corners $x_2^q$ of each cell and transitions via $f(x_2^q,u,d_2^m)$ (the maximum disturbance); the lower-sparse abstraction keeps lower corners $x_1^q$ and transitions via $f(x_1^q,u,d_2^m)$. Monotonicity ensures these two extreme transitions dominate every concrete transition from the cell, yielding the two ASUAS inequalities. The conservativeness results rest on Lemma 1, which uses the derivative bounds $0 \\leq \\partial f_i/\\partial x_j \\leq \\alpha_{ij}$ to show that a cell of width $\\eta$ can be compensated by a perturbation $\\varepsilon = \\alpha\\eta$.","core_discovery":"For a discrete-time monotone control system whose state space is lower closed, the upper-sparse abstraction $U_\\Sigma$ and lower-sparse abstraction $L_\\Sigma$ built from the same partition satisfy $U_\\Sigma \\preceq^0_u S_\\Sigma \\preceq^0_u L_\\Sigma$. Consequently, controller synthesis for $U_\\Sigma$ is sound (any abstract controller refines to the concrete system) and the absence of a controller for $L_\\Sigma$ is a certificate of impossibility for the concrete system. When data points are sampled under the maximum disturbance, data-driven versions $U_{\\Sigma_D}$ and $L_{\\Sigma_D}$ satisfy $U_{\\Sigma_D} \\preceq^0_u U_\\Sigma \\preceq^0_u S_\\Sigma \\preceq^0_u L_\\Sigma \\preceq^0_u L_{\\Sigma_D}$, giving the same two-sided guarantee without an explicit model. Theorems 3 and 5 give explicit inequalities, $\\varepsilon_i \\geq \\sum_j \\alpha_{ij}\\eta_j$, that translate a desired precision into a required discretization parameter in both the model-based and data-driven settings.","pith_inferences":["The bracketing idea should transfer to mixed-monotone systems, where extremal decompositions replace plain monotone bounds; the ASUAS relation's order-only condition is a natural fit.","The completeness guarantee suggests a practical synthesis workflow: start coarse, attempt upper synthesis, and if it fails refine until either a controller is found or the lower abstraction also fails, with the gap provably shrinking.","For upper-closed specifications, a mirror-image construction swapping the roles of $U_\\Sigma$ and $L_\\Sigma$ is implied by the paper's remark that analogous results hold, though the details are not worked out.","The probabilistic sample bound could be turned into an adaptive stopping rule: sample until every cell's critical region is hit rather than fixing $N$ in advance, potentially reducing data cost."],"forward_implications":["Safety controllers synthesized on the upper-sparse abstraction can be refined to the original monotone system without loss of correctness.","If the lower-sparse abstraction admits no controller for a lower-closed specification, the original system admits none, so controller-synthesis tools can now give negative answers with certainty.","The conservativeness gap between the two abstractions shrinks to any prescribed precision $\\varepsilon$ by refining the grid according to $\\varepsilon_i \\geq \\sum_j \\alpha_{ij}\\eta_j$.","Data-driven versions built purely from finite samples inherit both guarantees, so no model equations are needed while preserving soundness and completeness.","With uniform random sampling, the same guarantees hold with probability at least $1-\\beta$ once the sample count exceeds the bound in Proposition 2."],"supporting_citations":[{"why":"Supplies the standard symbolic-control refinement framework that the paper extends with a complete abstraction pair.","marker":"[1]"},{"why":"Gives a prior sound abstraction for monotone systems that the paper contrasts with its complete pair.","marker":"[7]"},{"why":"Provides the mixed-monotone abstraction construction and the interval-partition convention used in the sparse abstractions.","marker":"[8]"},{"why":"Establishes a data-driven model for monotone systems that the paper generalizes to data-driven complete abstraction pairs.","marker":"[22]"},{"why":"Introduces the upper alternating simulation relation for monotone systems that ASUAS relaxes and strengthens in specific ways.","marker":"[25]"},{"why":"Identifies the fragment of linear temporal logic specifications that are lower closed, used as the specification class for refinement.","marker":"[26]"},{"why":"Provides the definition of monotone dynamical systems and the Kamke-Mueller sufficient condition used in the model-based results.","marker":"[27]"},{"why":"Supplies the vehicle-following model and the Cartesian partition technique used in the numerical illustrations.","marker":"[36]"},{"why":"Provides the lazy controller synthesis algorithm used to compute the maximal safety controllers in the examples.","marker":"[37]"}],"fun_headline_variants":["Two abstractions bound control synthesis and impossibility","Data-driven abstractions bracket monotone systems","Complete pair: sound refinement and impossibility proof","Coarse abstractions pin down controller existence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The data-driven guarantees hold only when the partition respects the partial order (cells' upper bounds are ordered whenever the cells are ordered); a non-monotone partition can break the bracketing even when all other assumptions hold.","fun_headline_variants_meta":{"raw":{"variants":["Two abstractions bound control synthesis and impossibility","Data-driven abstractions bracket monotone systems","Complete pair: sound refinement and impossibility proof","Coarse abstractions pin down controller existence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00036,"raw_usage":{"total_tokens":1939,"prompt_tokens":933,"completion_tokens":1006,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":549,"completion_tokens_details":{"reasoning_tokens":951}},"tokens_in":549,"tokens_out":1006,"duration_ms":9382,"temperature":1.0,"reasoning_tokens":951,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:27:24.036905+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the data-driven construction on a monotone system using a non-monotone partition, for example two adjacent cells with ordered upper corners but crossed lower corners as in the third partition of Figure 3, and check whether $U_{\\Sigma_D} \\preceq^0_u U_\\Sigma$ still holds; a single transition where the data-driven successor jumps above or below the model-based successor would refute Theorem 4 as stated.","supporting_citations":[{"cited_title":"Compositional abstraction and safety synthesis using overlapping symbolic models,","cited_arxiv_id":null,"evidence_quote":"Gives a prior sound abstraction for monotone systems that the paper contrasts with its complete pair."},{"cited_title":"Efficient finite abstraction of mixed monotone systems,","cited_arxiv_id":null,"evidence_quote":"Provides the mixed-monotone abstraction construction and the interval-partition convention used in the sparse abstractions."},{"cited_title":"Data-driven models of mono- tone systems,","cited_arxiv_id":null,"evidence_quote":"Establishes a data-driven model for monotone systems that the paper generalizes to data-driven complete abstraction pairs."},{"cited_title":"Symbolic control design for monotone systems with directed specifications,","cited_arxiv_id":null,"evidence_quote":"Introduces the upper alternating simulation relation for monotone systems that ASUAS relaxes and strengthens in specific ways."},{"cited_title":"Directed specifications and assumption mining for monotone dynamical systems,","cited_arxiv_id":null,"evidence_quote":"Identifies the fragment of linear temporal logic specifications that are lower closed, used as the specification class for refinement."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the definition of monotone dynamical systems and the Kamke-Mueller sufficient condition used in the model-based results."},{"cited_title":"Contract-based design of symbolic controllers for safety in distributed multiperiodic sampled- data systems,","cited_arxiv_id":null,"evidence_quote":"Supplies the vehicle-following model and the Cartesian partition technique used in the numerical illustrations."},{"cited_title":"Lazy controller synthesis for monotone transition systems and directed safety specifications,","cited_arxiv_id":null,"evidence_quote":"Provides the lazy controller synthesis algorithm used to compute the maximal safety controllers in the examples."}],"review_version":1}