Control Closure Certificates

Vishnu Murali (✉), Mohammed Adib Oumer, and Majid Zamani · 2025

Read Control Closure Certificates by Vishnu Murali (✉), Mohammed Adib Oumer, and Majid Zamani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-03947.txt.

Introduction

Vishnu Murali, Mohammed Adib Oumer, and Majid Zamani introduce, in a 2025 paper, control closure certificates for building controllers with formal guarantees. The targets are endless-horizon rules, such as visiting a zone again and again forever. Standard proofs mix invariants with ranking arguments that show progress must end.

Closure certificates replace single rankings with disjunctive ones: several partial progress proofs that jointly force the goal. The authors show how to build such certificates for visiting a region endlessly, or only finitely often. Combining the two handles parity rules, the general form of such specs. A sum-of-squares search can then synthesize the certificate, and with it a controller that provably enforces the rule. Tests show the method designing working controllers.

Catalog record

CREATORVishnu Murali (✉), Mohammed Adib Oumer, and Majid Zamani
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE84 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-03947

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Control Closure Certificates Vishnu Murali (✉), Mohammed Adib Oumer, and Majid Zamani Abstract This paper introduces the notion of control closure certificates ( C 3 \text{C}^{3} ) to synthesize controllers for discrete-time control systems against ω \omega -regular specifications. Typical functional approaches to synthesize controllers against ω \omega -regular specifications rely on combining inductive invariants (for example, via barrier certificates) with proofs of well-foundedness (for example, via ranking functions). Transition invariants, provide an alternative where instead of standard well-foundedness arguments one may instead search for disjunctive well-foundedness arguments that together ensure a well-foundedness argument. Closure certificates, functional analogs of transition invariants, provide an effective, automated approach to verify discrete-time dynamical systems against linear temporal logic and ω \omega -regular specifications. We build on this notion to synthesize controllers to ensure the satisfaction of ω \omega -regular specifications. To do so, we first illustrate how one may construct control closure certificates to visit a region infinitely often (or only finitely often) via disjunctive well-founded arguments. We then combine these arguments to provide an argument for parity specifications. Thus, finding an appropriate C 3 \text{C}^{3} over the product of the system and a parity automaton specifying a desired ω \omega -regular specification ensures that there exists a controller κ \kappa to enforce the ω \omega -regular specification. We propose a sum-of-squares optimization approach to synthesize such certificates and demonstrate their efficacy in designing controllers over some case studies. sec:keywords discrete-time control systems, transition invariants, control synthesis, \omega -regular properties, parity automata 1 Introduction We introduce a notion of control closure certificates to synthesize controllers for discrete-time control systems against \omega -regular specifications. Closure certificates [ 22 ] , are a functional analog of transition invariants to verify discrete-time systems against \omega -regular specifications. Unlike barrier certificates [ 27 ] , which seek to overapproximate the reachable states of a system, closure certificates are real-valued functions that seek to overapproximate the reachable transitions of a system. When used for safety specifications, such certificates often allow for much simpler templates [ 22 , Section 3.1] to prove safety when compared to traditional barrier certificates. When combined with proofs of well-foundedness [ 9 ] , such certificates may be leveraged to prove \omega -regular specifications. Similar to barrier certificates, one may automate the search for closure certificates via optimization techniques such as sum-of-squares (SOS) [ 25 ] , satisfiability modulo theory solvers (SMT) [ 10 , 21 , 12 ] , and neural networks [ 1 , 24 ] . In the above cases, one fixes the certificate to be within a template class, e.g. , polynomials of a fixed degree or neural networks of a fixed size, and then proceeds to search for such a certificate within the template class. We build on this work to show how one may simultaneously search for both a certificate, as well as a controller to ensure the satisfaction of a desired \omega -regular specification. To do so we first provide certificate conditions to ensure that a set is visited infinitely often, or that it is visited only finitely often. We then show how one may combine these proof techniques to design controllers for more general \omega -regular specifications. Functional proofs for \omega -regular specifications. Functional approaches to synthesize controllers for \omega -regular specifications rely on a combination of finding inductive invariants with well-foundedness arguments [ 11 , 2 , 8 ] . Such a proofs of well-foundedness, similar to proofs of termination [ 9 ] , can be reduced to finding an appropriate ranking function \mathcal{V} . To illustrate these approaches, let \mathcal{X} denote the set of states of the system, and assume that one is able to determine the exact reachable set of a system (denoted \mathsf{Reach} ), and let \mathcal{X}_{VF} be a set of states of a system that must be visited only finitely often. Consider a function \mathcal{V}:\mathcal{X}\to\mathbb{R} from the states of the system to the reals such that: \displaystyle\mathcal{V}(x^{\prime})\leq\mathcal{V}(x)-\xi, \displaystyle\text{ if }x\in\mathcal{X}_{VF}\cap\mathsf{Reach}\text{ and } \displaystyle\mathcal{V}(x^{\prime})\leq\mathcal{V}(x) \displaystyle\text{ if }x\in\mathsf{Reach}\setminus\mathcal{X}_{VF}, where x^{\prime} is the one-step transition from state x and \xi is some positive value. Then the existence of a function \mathcal{V} that is bounded from below and satisfies the above conditions provides a proof that the system visits the set \mathcal{X}_{VF} only finitely often. As one typically does not know the set \mathsf{Reach} , one instead tries to ensure that the above conditions hold over an inductive state invariant that overapproximates the set \mathsf{Reach} . The promise of such functional proofs lie in their automatability. One may effectively search for them via optimization [ 27 , 25 ] or learning-based [ 1 ] techniques. Transition invariants. In the above discussion we considered the existence of a single function \mathcal{V} to prove a set \mathcal{X}_{VF} is visited only finitely often. Practically, one may want to instead consider partitions over relevant sets and try to find independent ranking function arguments to prove this. Unfortunately, such a strategy fails to be sound in general. This insight was observed in [ 26 ] , which showed that one cannot prove a relation to be well-founded if it is a union of well-founded relations. However, it is possible to prove a relation is well-founded if its transitive closure (cf. Section 2 ) is disjunctively well-founded. To overapproximate the transitive closure, they introduced a notion of transition invariants , that overapproximate the reachable transitions of a system. Hence one is able to leverage transition invariants to find independent ranking functions to prove well-foundedness. While transition invariants provide an approach to prove a set is visited only finitely often, one often requires to show the dual, that a set be visited infinitely often, or both. This is the case when dealing with deterministic automata that describe \omega -regular languages such as Rabin, Streett, or parity automata. Thus, we consider the question of how disjunctive well-founded proofs help in designing controllers for \omega -regular specifications. Our Contributions. • We introduce a notion of control closure certificates to synthesize controllers for discrete-time control systems against \omega -regular specifications. • We show how proofs of disjunctive well-foundedness are useful not just for showing a set is visited only finitely often but also in proofs of showing a set is visited infinitely often, thus making them amenable to provide conditions for synthesis against \omega -regular properties. • We rely on an optimization-based approach to automate the search for these control closure certificates and demonstrate their use in some case studies. Related works. The results in [ 27 ] introduced a notion of barrier certificates to act as functional inductive invariants for hybrid systems. These results illustrated how one may effectively automate the search for such such certificates via optimization techniques such as sum-of-squares programming [ 25 ] . Building on this idea, the results in [ 11 ] considered a notion of parity certificates to synthesize controllers for objectives specified by parity automata and then demonstrated how one may use such certificates in verifying alternating-time temporal logic properties [ 4 ] . These certificates relied on a combination of invariant arguments (characterized as barrier certificates) with ranking functions (described as Lyapunov functions) to design controllers. Similar to these results, the results in [ 2 ]

Read the complete text