CS Paper Radar

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

Kodai Kanno, Kenta Hoshino, Takeshi Hatanaka

eess.SY ·submitted 2026-09-20 11:55 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Computing GR(1) Assume-Guarantee Contracts

cs.LO eess.SY ·2026-10-27 ·Yigit Narter, Emily Zhao, Inigo Incer
similarity 0.63
Abstract · 55 pages, 10 figures

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.

0.23

Compiling Sufficient Governance Context from Declared Losses and Reachable States: Exact Observation-Contract Synthesis with Cardinality and Cost Objectives

cs.SE cs.AIcs.LO ·2026-09-22 ·Gaston Besanson
code/data similarity 0.61
Abstract · Code, data, preregistration tags, review record, and independent reproduction (repository issue #3): https://github.com/besanson/sarc-author…

We call the object this paper derives and certifies a minimal sufficient governance context: given a finite reachable-state model, a deterministic declared verdict, and candidate observable attributes, we compute sufficient observation sets, distinguish attributes that are individually indispensable from contracts that are jointly sufficient, and select among sufficient contracts under a cardinality or declared-cost objective. An observation contract is a set of candidate attributes whose values determine the declared verdict on every reachable state; an authority contract is one selected under an objective and bound to a gate schema. We synthesize every inclusion-minimal sufficient contract where exhaustive enumeration is affordable, and a minimum-cardinality or minimum-cost contract by SAT/MaxSAT encoding otherwise, checking sufficiency directly. On a constructed code/cloud domain, the individually-indispensable core is not sufficient as an observation contract and two distinct reducts exist; a preregistered cost model separates them exactly. On a second, larger, constructed domain, the same pattern recurs, but that domain's cost model does not separate the alternatives: a fully explained cost tie, reported as found. We measure discernibility-family scaling where exhaustive enumeration is confirmed infeasible within a registered timeout, while SAT/MaxSAT synthesis solves in well under a second; MaxSAT showed no measured cardinality advantage over plain SAT. AuthorityBench compares four baselines across three domains; the declared-only baseline is not exactly sufficient on any. Every selected contract is checked for sufficiency, with a counterexample on failure and a check summary, not a portable certificate, on success -- the compiler-focused scope of a two-scope table; an independently specified end-to-end case study is registered follow-up work, not claimed here.

0.57

Satisfiability Modulo Theories for Robust Synthesis of Signal Temporal Logic Specifications

eess.SY cs.RO ·2026-11-17 ·Philip Smith, Kevin Leahy
similarity 0.61
Abstract · Submitted to American Control Conference

Signal Temporal Logic is a popular framework for describing a robotic system's goals. Once described using a temporal logic framework, synthesis turns the goals into actual steps for the robots to follow. Currently, the state of the art for sound and complete synthesis is using Mixed-Integer Linear Programming (MILP), which struggles on long time horizons and large environments, preventing the construction of guaranteed safe plans for long deployments. This paper introduces a new synthesis method using Satisfiability Modulo Theories (SMT) which scales better for long deployments and adapts to environmental changes more quickly. We do this by introducing an encoding method for STL into SMT constraints, and an encoding method for discrete-time dynamical systems modeled as a transition system. We then conduct an empirical comparison of our SMT based methods against the state of the art MILP based methods. Results show that for this class of problems, SMT is an effective encoding strategy that performs the best on long time horizon tasks.

0.24

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.60
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

Runtime Monitoring of Distributed Cyber-Physical Systems Without a Global Clock

cs.LO ·2026-08-13 ·Charles Koll, Houssam Abbas
published similarity 0.59
Abstract · Accepted to Runtime Verification 2026

We give the first theoretical characterization, and the first algorithm, for continuous monitoring of a distributed Cyber-Physical System (CPS) against a dense-time temporal logic specification. A distributed CPS is composed of multiple agents, each with a local clock; these clocks drift from each other, so there is no well-defined global time. When monitoring such a system's output signal against a temporal logic specification, it is not evident how to interpret the temporal constraints of the formula, and what satisfaction means. Yet CPS designers, like control engineers, typically think of their system's operation in terms of global time. Most existing techniques for monitoring distributed systems work with discrete-time specifications not suitable for CPS, and/or require an explicit mapping of temporal constraints to local clocks. We introduce an algorithm that addresses the above challenges for a fragment of Signal Temporal Logic (STL) that still includes all temporal operators. It relies on a novel extension of satisfaction signals to this partially synchronous setting (where clocks drift), and an analysis of the geometry of multi-dimensional partially synchronous time. The algorithm returns the set of all possible global moments that can satisfy the specification. Knowledge of these possible global moments is important for debugging distributed hybrid control systems such as fleets of drones and electrical grids. We derive the worst-case complexity of the algorithm, and implement a sound approximation of it that experimentally illustrates effective monitoring, even in scenarios of up to 50 agents.

0.23

Distributed LTL Synthesis under Arbitrary Message Adversaries

cs.DC cs.FLcs.LOeess.SY ·2026-11-03 ·Benedikt Bollig, Patricia Bouyer-Decitre, Matthias Függer, Dhrubajyoti Ghosh, Thomas Nowak +1 more
similarity 0.59
Abstract

Reactive synthesis is the problem of generating a program that produces outputs satisfying a logical specification for every input stream. We study distributed synthesis for two processes communicating in rounds over unreliable links, with at least one message delivered in every round. Despite this delivery guarantee, we show that synthesis from linear temporal logic specifications is undecidable, even when messages carry the processes' complete causal histories. More generally, we give a complete characterization of the communication restrictions that make synthesis decidable. Restrictions are described by a message adversary $A$, a set of allowed infinite graph histories: sequences of communication graphs, each specifying which messages are delivered in a round. Iterated chromatic subdivision associates these histories with points in the unit interval, yielding an image $π(A) \subseteq [0,1]$. For every $ω$-regular message adversary $A$, synthesis is decidable if and only if $π(A)$ is nowhere dense. In the decidable cases, our procedure takes a deterministic parity automaton for $A$ and a specification, decides realizability, and constructs a realizing distributed algorithm whenever one exists. Further, our topological arguments shed new light on the fundamental requirements of synthesis. They show that, for $ω$-regular message adversaries, synthesis is decidable if and only if consensus is repeatedly solvable in bounded time. This links two previously unrelated problems from formal verification and distributed computing through the processes' uncertainty about communication.

0.22

A Pragmatic Guide to Building Conservative Discrete Abstractions of Cyber-Physical Systems

eess.SY cs.LO ·2026-08-10 ·Jordan Peper, Krish Kapadia, James Gast, Ethan Howes, Ivan Ruchkin
similarity 0.58
Abstract

Symbolic model checking is an effective approach for verifying semantically rich temporal-logic properties of cyber-physical systems, but it hinges on discretizing continuous-state dynamics into a finite-state abstraction. To transfer verification guarantees from the abstract model to the concrete CPS, the abstraction must conservatively approximate the concrete state space and behaviors. Hence, model-builders must maintain this soundness while balancing pessimism with tractability. However, they face several common pitfalls such as under-approximating the state space, under-approximating transitions, unsound pruning of "degenerate" behaviors, and improper specification lifting. This tutorial presents a pragmatic, conservative-by-construction workflow for building discrete abstractions of closed-loop dynamical systems. The workflow consists of four modular steps with interchangeable subroutines: (i) state-space partition and abstraction-function design, (ii) conservative transition construction via axis-aligned bounding boxes, polytopes, or sampling with PAC coverage certificates, (iii) mitigation of spurious transitions and self-loops using certified erasure and counterexample-guided abstraction refinement, and (iv) sound lifting of LTL specifications using may-must semantics. We demonstrate the end-to-end pipeline on three case studies and report how these design choices affect abstraction structure, runtime, and verification outcomes.

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.57
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