CS Paper Radar

Complexity of Local Observation Consistency in Discrete-Event Systems

Tomáš Masopust

eess.SY ·submitted 2026-08-10 18:30 UTC · v1

Abstract

Hierarchical and multi-agent supervisory control under partial observation relies on local consistency conditions between a plant and its abstraction: local observation consistency (LOC) for the projection abstractions of hierarchical control, and local relabeling observation consistency (LROC) for the relabeling abstractions of multi-agent systems. Both are companions to a global condition and both have been used without their verification complexity being settled. We show that both are PSpace-complete for nondeterministic plants and decidable in polynomial time for deterministic plants.

Closest papers

Nearest neighbours by meaning across the whole index.

Supervisory Control under Partial Observation: Where Observation Consistency Becomes Decidable

cs.FL ·2026-09-06 ·Shaowen Miao, Jan Komenda, Tomáš Masopust, Yiding Ji
similarity 0.81
Abstract · Submitted to a journal on August 21, 2026

Observation consistency (OC) and modified observation consistency (MOC) are structural conditions used in hierarchical and modular supervisory control under partial observation. Their verification for languages generated by deterministic finite automata is PSPACE-hard, whereas decidability was open. We answer this question by showing that both problems are undecidable, that is, there are no algorithms verifying OC or MOC. On the positive side, we identify a decidable class defined by a restriction on the plant: if every cycle of the automaton contains a transition labeled by an observable high-level event, then verification of both conditions is PSPACE-complete.

0.28

Deciding Relabeling Observation Consistency in Multi-Agent Discrete-Event Systems

eess.SY ·2026-08-19 ·Tomáš Masopust
similarity 0.77
Abstract

Scalable supervisors for multi-agent discrete-event systems control groups of isomorphic agents through a common template. Under partial observation, such a supervisor is maximally permissive if the relabeling that maps the agents onto their template is relabeling observation consistent (ROC) and a local companion condition holds. Whether ROC is decidable was open. We show that it is PSPACE-complete: for nondeterministic plants with two observable and one unobservable event, and for deterministic plants with two observable and two unobservable events. On the tractable side, we characterize the relabelings that guarantee ROC for every plant, we give a polynomial-time algorithm for deterministic plants whose relabeling is injective on unobservable events, and we give sufficient conditions based on saturation and on simulation, with polynomial-time tests for both. We further show that ROC is compositional for components with pairwise disjoint templates, with equivalence if the alphabets are moreover pairwise disjoint, and that neither hypothesis can be dropped. Finally, we show that the structural condition proposed in the literature to guarantee ROC is incorrect, and repair the companion inclusion that the same proposition asserts.

0.09

Policy Change for Treelike Monitors

cs.LO ·2026-09-09 ·François Hublet, Dhruv Nevatia, Joshua Schneider
similarity 0.54
Abstract · 39 pages, 5 figures

We study the policy change problem that arises in the runtime verification of long-running systems. The online monitors typically used in this context are generally treelike, in that they maintain substates that monitor subformulae of the target policy. We consider when and how the policy can be changed while the monitored system is running by only exploiting the information stored in the monitor's state. This is relevant, for example, to account for new system functionality or changes in regulatory requirements. We formally define the policy change problem in a general setting, independent of any specific (treelike) monitor implementation. We then show that policy change for past-time metric temporal logic (pMTL) is decidable but has tight non-primitive recursive lower and upper bounds, while with discrete-time semantics it is EXPSPACE-complete.

0.28

Observer-Based Control for Multi-Agent Systems under Communication-Task Graph Mismatch and Directed Switching Topologies

eess.SY ·2026-10-20 ·Tommaso Zaccherini, Siyuan Liu, Dimos V. Dimarogonas
theory similarity 0.54
Abstract

This paper addresses decentralized estimation and control of heterogeneous multi-agent systems communicating over directed switching topologies. The objective is to satisfy cooperative tasks that require coordination among agents according to a time-invariant task graph. To address the potential mismatch between the communication and task graphs, each agent is equipped with a k-hop Prescribed Performance State Observer (k-hop PPSO) to estimate the states of agents up to k communication hops away using only information exchanged with its 1-hop neighbors. A novel prescribed performance funnel construction is developed to account for the switching communication topology, and a sufficient lower bound on the dwell-time is derived to guarantee the prescribed performance specifications under topology variations. Further analysis shows that, if the desired control objective is achieved with exact knowledge of the required nonlocal states and the resulting closed-loop system is uniformly set-ISS with respect to the state estimation error, then replacing these states with their estimates guarantees convergence to a neighborhood of the desired set. The size of this neighborhood can be made arbitrarily small by appropriately selecting the observer performance bounds. A simulation study demonstrates task satisfaction under directed switching topologies.

0.22

A Distributed Observer with Random Agent Activations over Random Communication Networks

eess.SY ·2026-11-08 ·Yong Joo Do, Jin Gyu Lee
similarity 0.50
Abstract

This paper develops a distributed observer for the forward-Euler discretization of a continuous-time linear time-invariant system under random local operations and random communications. Under uniform stochastic strong connectivity, we establish almost sure exponential convergence of all local state estimates for sufficiently small discretization step sizes. We further examine how the underlying parameters and components affect the admissible range of the discretization step size and the guaranteed convergence rate bound. Unlike related approaches, the proposed method does not require each local unobservable subspace to admit an $A$-invariant complement.

0.26

Verifying Control Invariance of H-Polytopes is coNP-Complete

eess.SY math.OC ·2026-10-27 ·Mario Eduardo Villanueva, Boris Houska
theory similarity 0.50
Abstract

We prove that verifying whether an H-polytope is control invariant for a discrete-time linear system with polytopic input constraints is \textsc{coNP}-complete. This establishes a fundamental computational complexity barrier for set-theoretic control. As an immediate consequence, the exact computation of maximal control invariant subsets of H-polytopes is \textsc{coNP}-hard. These hardness results hold regardless of whether the input constraint set is given in H- or V-representation.

0.28

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

cs.LO ·2026-08-13 ·Charles Koll, Houssam Abbas
published similarity 0.50
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

The existence of polyhedral invariants is undecidable for linear systems

cs.LO ·2026-09-25 ·David Monniaux
similarity 0.49
Abstract

The existence of polyhedral inductive invariants suitable for proving that a given control location is unreachable is undecidable for programs using only linear arithmetic over Z or Q, by reduction from 2-counter machines.

0.30