CS Paper Radar

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

Tomáš Masopust

eess.SY ·submitted 2026-08-19 12:36 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Complexity of Local Observation Consistency in Discrete-Event Systems

eess.SY ·2026-08-10 ·Tomáš Masopust
similarity 0.77
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.

0.34

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

A Minimum Exact Disjunctive Basis for Two-Robot Solvability Profiles

cs.DC cs.ROmath.CO ·2026-10-13 ·Tsukasa Ninomiya, Shota Naito, Naoki Kitamura, Yuichi Sudo, Koichi Wada
theory similarity 0.55
Abstract · 100 pages, 2 figures, 9 tables

We completely characterize the solvability profiles of tasks for two autonomous mobile robots in the plane under variable disorientation, chirality, and rigid movements. The four standard capability models and the schedulers considered here have a known quotient order Q of thirteen computational classes. A task's solvability profile is the set of classes in which it is solvable, and is necessarily an upset of Q. We prove that every upset is realizable and construct a minimum exact disjunctive basis of thirteen concrete tasks. The basis contains one task for each principal upset. For every antichain of Q, the disjunction of the corresponding tasks has profile exactly equal to the union of their profiles. This exactness is not implied by the individual profiles: an algorithm may satisfy different disjuncts in different executions. We establish it by constructing, for every algorithm in each maximal class outside the target union, a single admissible fair execution violating all selected predicates simultaneously. Consequently, the realizable profiles form the entire finite distributive lattice Up(Q): there are exactly 54 profiles, counted by the antichain polynomial 1 + 13z + 24z^2 + 16z^3, and each has a canonical disjunctive representation using at most three principal tasks. We also identify six tasks whose solvability signatures recover every inclusion and incomparability in Q, and prove that six is minimum even among arbitrary separating tasks. Their profiles are precisely the principal upsets generated by the join-irreducible elements of Q. In contrast, any task family generating every profile by exact disjunctions must contain all thirteen principal profiles. Thus our exact disjunctive basis has minimum size and is unique at the profile level.

0.33

Verification of $K$- and Infinite-Step Strong/Weak Anonymity Using Concurrent Compositions

cs.FL cs.CR ·2026-09-01 ·Jiahui Zhang, Kuize Zhang, Xiaoguang Han, Zhiwu Li
similarity 0.55
Abstract

Anonymity is an information flow property that provides privacy protection in the sense of non-uniqueness of system information at certain moments with respect to observations. The notion of $K$-step anonymity in the context of discrete-event systems characterizes the scenario that the state estimates cannot be a singleton within at most $K$ observational steps prior to the current instant, while infinite-step anonymity is the same as $K$-step anonymity without considering the limit on $K$. In this paper, we lucubrate $K$- and infinite-step anonymity for partially-observed discrete-event systems modeled by non-deterministic finite-state automata. First, we define two strong types and two weak types of $K$- and infinite-step anonymity that are fundamentally different from the existing notions of $K$- and infinite-step anonymity due to the consideration of strong and weak anonymous projections. Then, we develop a new methodology by exploiting the concurrent-composition technique to verify these four types of anonymity. Based on the constructed concurrent compositions, verifiable necessary and sufficient conditions for the four types of anonymity are provided, along with their complexity analysis. Finally, the upper bounds on $K$ for $K$-step strong anonymity and weak anonymity are computed.

0.22

Parameterized Reachability for Register Machines with Data

cs.FL ·2026-10-06 ·Parosh Aziz Abdulla, Mohammed Faouzi Atig, Abhijith R Nair, K Narayan Kumar, Prakash Saivasan
similarity 0.55
Abstract

We investigate the parameterized reachability problem for concurrent register machines over infinite data domains. In this framework, each machine is a program equipped with a set of local registers, the communication across machines is mediated through a set of shared registers. Both local and shared registers can take values from an infinite data domain. The program's primitive operations include copying values between registers, assigning constants, comparing registers for (dis-)equality, and nondeterministic assignments that store an arbitrary domain value into a local register. The parameterized reachability problem considers a program and a target location, asking whether there exists some n in Naturals such that an execution of n identical machines (referred to as instances) results in at least one instance reaching the specified location. We show that this problem is Pspace-complete in the general case and it becomes undecidable if a freshness assumption (i.e., each assignment must produce a unique value distinct from all constants) is applied to nondeterministic assignments. This undecidability persists even for systems restricted to two shared and two local registers. Finally, we establish optimal decidability results for two restricted settings: when each thread is limited to a single local register, or when the system utilizes only one shared register.

0.30

Certified Task-Conditioned Active Observability

cs.AI stat.MLcs.LG ·2026-09-22 ·Linzhe Zhang, Changming Xu
theory similarity 0.55
Abstract

Before acting upon an unobservable physical system, an autonomous agent must determine which latent distinctions govern downstream tasks, how many active interventions are necessary to certify them, and when to abstain to prevent catastrophic errors. Classical observability treats state reconstruction as an unconditioned binary predicate, failing when passive observations cannot break latent degeneracies without perturbation, full microscopic inversion is prohibitively costly, and distinguishing task-irrelevant degrees of freedom wastes interaction budgets. We formalize task-conditioned active observability complexity: the minimum worst-case expected interaction cost required to identify task-relevant states under certified error and safe abstention guarantees. We prove that task-predictive equivalence induces the unique minimal sufficient quotient $\mathcal{H}/\!\sim_τ$, leaving active observability complexity strictly invariant while eliminating superfluous distinctions. In deterministic regimes, this complexity is characterized by an optimal adaptive distinguishing tree and Bellman recursion; in noisy regimes, it obeys a stopped-transcript relative-entropy lower bound and adaptive martingale certificates that compose without independence assumptions. We instantiate a prospective certified observer with staged recovery: a nominal verifier defers candidate compilation, triggering active probing only upon evidence, while a history-measurable score shell prunes hypotheses without sacrificing risk bounds. Stress audits across high-dimensional physical systems and thousands of operational trials demonstrate certified state recovery with zero false acceptances and substantial reductions in sensor reads and model steps.

0.36

The existence of polyhedral invariants is undecidable for linear systems

cs.LO ·2026-09-25 ·David Monniaux
similarity 0.54
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

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