CS Paper Radar

Computing GR(1) Assume-Guarantee Contracts

Yigit Narter, Emily Zhao, Inigo Incer

cs.LO eess.SY ·submitted 2026-10-27 16:53 UTC · v2

Abstract

Assume-guarantee contracts provide a set of algebraic operations that enable the efficient compositional design and analysis of complex engineering systems. The explicit computation of these operations at component interfaces is currently supported only for some logics lacking a notion of time. This paper develops theory and algorithms to compute these operations when the contracts are expressed in the GR(1) modulo theory. The key challenge is the computation of two quantifier elimination problems for temporal formulas. We develop context-aided variable elimination procedures on GR(1)-modulo formulas, establish their soundness, characterize subproblem-wise optimal solutions within an admissible class of formulas, and use the procedures to compute contract operations, including composition and quotient. We implement the resulting framework in Pacti, automating compositional reasoning over GR(1) contracts. Finally, we demonstrate the framework on an automated emergency-braking case study, where we compute system-level contracts and expose compatibility conditions arising from the interaction of component specifications. Experiments on synthetic families show that the cost is governed by the number of eliminated variables and liveness conjuncts, and a comparison with exact automata-based elimination shows complementary scaling.

Comment
55 pages, 10 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Contract-Based Decomposition of Temporal Logic Specifications for Networked Systems under Arbitrary Partitions

eess.SY ·2026-09-20 ·Kodai Kanno, Kenta Hoshino, Takeshi Hatanaka
similarity 0.63
Abstract

Computational complexity is an inherent limitation of formal synthesis for networked systems, and decomposing the global specification into local ones relaxes this limitation at the cost of conservatism. Since the granularity of the partition governs this trade-off, it is reasonable to treat the partition as a design variable, which calls for local specifications that remain correct for every partition. To this end, this paper gives each agent a local specification, written as an assume-guarantee contract that the agent can establish from local information. We first derive a necessary and sufficient condition for these contracts to decompose the global specification under a given partition. Building on this, we then present a condition under which the decomposition is correct for every partition, so that the partition becomes a free design variable. For linear dynamics and signal temporal logic formulas with affine predicates, we further synthesize a controller for each coalition by a tube-based approach. Finally, simulations on a network of input-coupled tanks show how the choice of partition trades computational cost against conservatism.

0.19

Learning to adapt GR(1) specifications through degradation

cs.SE cs.AIcs.LO ·2026-09-10 ·Tiberiu-Andrei Georgescu, Dalal Alrajeh, Sebastian Uchitel
similarity 0.60
Abstract · 59 pages (39 pages main text, 20 pages appendices), 24 figures, 5 tables. Submitted to ACM Transactions on Software Engineering and Methodol…

Reactive synthesis is a powerful tool for generating correct-by-construction controllers from formal specifications. GR(1) is an assume-guarantee specification framework that enables efficient synthesis, allowing synthesised controllers to be used in a wide array of applications. The limitation of such controllers is that, should they encounter environment behaviour unspecified in the assumptions of the specification, the specified system guarantees are no longer ensured. Our work proposes an approach based on oracle-guided inductive synthesis to adapt the specification to be consistent with the observed assumption violation, while degrading system guarantees as little as possible to maintain realisability. Our methodology discovers multiple potential solutions, so we propose a preference criteria, based on the ability of the specification to enable robustness under adaptation. Although our approach is capable of degrading the entire specification, for our case studies we successfully discover degradations that preserve the entire set of original guarantees.

0.15

Multimodal Logic Programming with Full Formulas

cs.LO math.LO ·2026-08-14 ·Kenji Tokuo
similarity 0.58
Abstract

This paper presents a first-order multimodal logic programming system called MMLP. The system accepts arbitrary formulas as both programs and queries, without restricting either side to Horn clauses or a separate goal grammar. Its declarative semantics is given independently by a Hilbert system for selected D, T, I, B, 4, and 5 modal principles. Execution uses a nested proof calculus with finite grammar certificates for modal propagation. Certificate reachability is equivalent to the associated Horn closure, certificate existence is decidable, and the calculus is cut-free complete. For quantified answer computation, we give a unification algorithm based on permission sets that controls eigenparameter scope. The algorithm always terminates and fails exactly when no admissible solution exists. A successful run returns a unifier that is itself admissible and through which all admissible solutions factor. Computed answers are declaratively correct, and each declaratively correct answer is an ordinary output instance of a computed answer. In proof search, MMLP admits syntactic focalization and a fair and complete enumeration of focused answers. It represents exactly the same answer substitutions as Nguyen's pure logical KDI4s5-MPROLOG on their common fragment, while admitting a strictly larger program and query language.

0.04

TLA-Verus: Generating and Solving Temporal Proof Obligations with LLM Agents

cs.LG ·2026-10-10 ·Kseniia Strelbytska, Balázs Szilágyi, Anna Mészáros, Ferenc Huszár
theory similarity 0.58
Abstract

The TLA+ (temporal logic of actions) formal specification toolkit has seen widespread adoption in modeling modern distributed software systems including databases, storage systems, ledgers and coordination protocols. This popularity is despite its two significant limitations for software verification: Firstly, TLA+ offers no way to detect drift between software implementation and mathematical specification; secondly, TLC and TLAPS cannot provide satisfactory proofs of arbitrary temporal logic properties. We address the second limitation and take a first step towards the first by translating TLA+ specifications into Verus, an auto-active verifier built for Rust, via both a deterministic transpiler and an agentic translator. We demonstrate that our LLM-based pipeline is able to generate proof obligations from TLA+ specifications at scale, and to produce fully machine checkable proofs of both safety and liveness properties. Since temporal logic reasoning in Verus is a largely new task for LLMs, our work yields a valuable evaluation dataset, which we use to map out current generation model capabilities in Verus theorem proving.

0.35

Contract-Based Agentic Systems Engineering: Delegation as Quotient for Assured System Design

eess.SY cs.RO ·2026-10-23 ·Sai Sandeep Damera, Ryan Matheu, John S. Baras
similarity 0.57
Abstract

A component an agent builds from a prompt can satisfy it and still break the system it joins, because the prompt omits what its neighbours assume of it. The artifact to hand over is computed, not written. A SysML v2 requirement with assumed and required constraints is an assume/guarantee contract, so when a system requirement is decomposed over fixed neighbours, the open component's requirement is the contract quotient, the weakest sound one, and again a SysML v2 requirement. Its required constraints carry the neighbours' assumptions, which a requirement for the mission alone drops and unit tests with mocked neighbours cannot reach. Signal Temporal Logic is closed under the quotient. We build the requirements, with derivation, allocation, satisfaction and verification, as a SysML~v2 model and compute the quotient from it. A case study delegates the local controller of a simulated warehouse robot, whose route crosses a worker's path and ends at a dock, to one language model under the quotient requirement, a mission-only requirement and a natural-language task, and scores the deliveries on live episodes against the system requirement from ground truth.

0.14

Extending SMT Solving with Non-Ground Clause Learning

cs.AI cs.LO ·2026-09-10 ·Yasmine Briefs, Christoph Weidenbach
theory similarity 0.57
Abstract · Extended version of LPAR 2026 paper

Quantifier instantiation is currently the main approach to non-ground SMT solving: solvers generate ground instances and solve the resulting ground SMT problems with CDCL(T)-style reasoning. When a conflict is found, conflict analysis learns only a ground clause, even though the conflict comes from instances of non-ground clauses. Yet non-ground reasoning can give exponentially shorter proofs than purely ground reasoning. We propose a calculus that consists of ground instantiations, CDCL(T)-style rules, and non-ground conflict analysis. The solver reasons on ground instances, but the resolution steps of conflict analysis are performed on their original non-ground clauses. This produces learned clauses that are typically more general than the ground conflict. With a suitable strategy, the learned clauses are even non-redundant. We also show how chronological backtracking can be included in SMT solving. Our calculus gives a common setting for CDCL(T)-style SMT solving, a range of instantiation-based procedures, and non-ground clause learning, and we prove that it simulates CDCL, SCL(FOL), SCL(T), and even Resolution.

0.14

Formal Verification of Proofs from Automated Theorem Provers for Higher-Order Logic

cs.LO ·2026-09-21 ·Melanie Taprogge, Frédéric Blanqui, Alexander Steen
top venuetheory similarity 0.57
Abstract

We identify common challenges and requirements for verifying proofs from automated theorem provers in the Dedukti logical framework and develop a general methodology for deriving encodings of calculus rules and proof steps, including clausification. We then apply this methodology to the EP calculus for higher-order logic and integrate it into the automated theorem prover Leo-III. The resulting prototype reconstructs about 80% of generated proof steps automatically, making Leo-III the first higher-order automated theorem prover to support independently checkable proof reconstruction and providing a basis for cross-system reuse. The implementation uncovered several bugs in Leo-III.

0.71

Symbolic Execution of Constrained Horn Clauses

cs.LO cs.PL ·2026-10-02 ·Johannes Weiser, Zafer Esen, Philipp Rümmer
similarity 0.57
Abstract · 34 pages, 8 figures

Constrained Horn clauses (CHCs) are a fragment of first-order logic widely used as an intermediate language for verification. We study constrained resolution as a calculus for reasoning about the satisfiability of sets of CHCs. Constrained resolution forms a simple alternative to model checking algorithms such as CEGAR and IC3 and is here shown to exhibit complementary features. We show that, when CHCs encode programs, forward symbolic execution corresponds to positive unit hyper-resolution, and backward symbolic execution to SLD resolution, which are special cases of constrained resolution. We formalize forward and backward reasoning for linear and non-linear CHCs and transition systems, prove refutational completeness under fair strategies, and develop subsumption criteria for pruning redundant derivations. We moreover show that backward resolution with subsumption generalizes $k$-induction to non-linear CHCs, and that forward constrained resolution is related to the problem of constructing proofs in incorrectness logic. Lastly, we provide an experimental evaluation in the Eldarica CHC solver on benchmarks from CHC-COMP.

0.19