CS Paper Radar

Resilience in labeled real-time automata

Kuize Zhang

cs.CC ·submitted 2026-09-07 05:21 UTC · v1

Abstract

In this paper, we characterize resilience for a labeled real-time automaton (LRTA). An LRTA is resilient if whenever a faulty event occurs, after sufficiently many events occur, the LRTA returns to normalcy and the occurrence of the faulty event is not leaked. The notion of resilience reflects the ability of an LRTA recovering from a faulty behavior, and hence can model an intelligent agent. We formulate one definition of resilience for an LRTA and give verification algorithms for the definition based on two basic tools --- concurrent composition and observer.

Comment
21 pages, 12 figures

Closest papers

Nearest neighbours by meaning across the whole index.

CA-Observability of Discrete Event Systems under Cyber Attacks

eess.SY ·2026-10-06 ·Shengbao Zheng, Shaolong Shu, Feng Lin
theory similarity 0.57
Abstract

In a previous paper, we investigate the control problem of discrete event systems under cyber attacks, where CA-controllability and CA-observability are proposed. We prove that a discrete event system can be controlled to generate a specification language K if and only if K is CA-controllable and CA-observable. While CA controllability can be "converted" to (conventional) controllability, CA-observability cannot be "converted" to (conventional) observability. In this paper, we further investigate CA-observability. We develop a method and an algorithm to check CA-observability. The method involves constructing an augmented automaton whose states are pairs of the current state and state estimate of the supervised system. We prove that K is CA-observable if and only if the language generated by the augmented automaton is equal to K. An algorithm is then developed to check CA-observability. We also investigate the properties of CA-observability. We show that CA-observability is not closed under (set) in tersection. Note that (conventional) observability is closed under intersection. We further show that CA-observability is not closed under union. This is similar to observability. If K is not CA-controllable and CA-observable, we pro pose a method to calculate a CA-controllable and CA observable sublanguage. We first calculate the supremal CA-controllable sublanguage for K which can be described by a sub-automaton of the automaton for K. We then propose a state-estimate-based supervisor based on the subautomaton, which ensures the supervised system stays within K.

0.23

Verse: Semantics and Verification of Hybrid Multi-Agent Scenarios

cs.FL ·2026-10-26 ·Yangge Li, Katherine Braught, Alex Yuan, Sayan Mitra
similarity 0.55
Abstract

Verifying cyber-physical systems with many interacting agents remains difficult because interactions are mediated by sensors, individual decisions are constrained by environment (map) structure, and the resulting mode space scales combinatorially. We present Verse, a framework for writing agents, maps, and sensors in a familiar programming language syntax, with a formal semantics for the resulting scenarios. A compiler translates each scenario to a hybrid automaton whose executions correspond exactly to the runs of the scenario. Reachability analysis on this automaton builds an execution tree from two post operators, one for continuous flow over a time step and one for a single agent's mode change, and checks safety assertions at every vertex. The tree expands only the modes that are reached, without enumerating the global mode space. Experiments highlight expressive modeling across cars and drones, 2D/3D maps (including OpenDRIVE imports), noisy sensors, and multiple simultaneous safety assertions. Verse verifies a scenario with 7 agents and 37 modes in 90 seconds on a standard laptop; it is competitive with CORA and JuliaReach on ARCH benchmarks, and on multi-agent scenarios is an order of magnitude faster than JuliaReach at the cost of looser reachable sets.

0.20

ResonAct: Streaming Metrics for Runtime Diagnosis and Self-Healing in Multi-Agent Systems

cs.AI cs.LG ·2026-09-28 ·Tarun Chintada, Neelamadhav Gantayat, Ishaan Romil, Renuka Sindhgatta, Soujanya Soni +1 more
similarity 0.55
Abstract

Multi-agent systems (MAS) are increasingly used to automate enterprise workflows involving multiple specialized agents, external tools, and long-running task execution. Failures may arise from tool degradation, context propagation errors, coordination breakdowns, or repeated agent interactions that prevent task completion. While existing observability frameworks provide traces and logs, diagnosis and remediation are largely performed after execution completes, limiting opportunities for recovery during runtime. We present ResonAct, a runtime self-healing framework that enables continuous monitoring, diagnosis, and remediation of multi-agent systems through streaming operational metrics. ResonAct ingests execution traces, agent interactions, and tool invocations into a streaming analytics layer that continuously derives task progress, context health, and tool reliability metrics. These metrics serve as runtime control signals for detecting anomalous execution patterns and localizing root causes using a structured failure model. Based on the diagnosed failure, ResonAct dynamically selects remediation policies and performs actions. The framework operates as an external control plane, enabling intervention without modifying application agents or orchestration logic. We evaluate ResonAct across enterprise workflow scenarios and AppWorld benchmarks. The results show that the streaming metric-based analysis identifies execution degradations and localizes faults. Furthermore, policy-driven remediation improves task completion rates by up to 10.00 percentage points, with detection precision ranging from 70.59% to 82.91%, recall from 63.09% to 100%, recovery rates from 10.48% to 46.67%, and runtime overhead ranging from $-0.25%$ to 14.12% across the evaluated configurations.

0.22

Compositional Automata Learning of Timed Synchronous Systems

cs.FL ·2026-10-15 ·Hanyue Chen, Chang Liu, Miaomiao Zhang
publishedbenchmarkcode/data similarity 0.54
Abstract · 32 pages, 26 figures, including appendices. Accepted at SETTA 2026. Code and data: https://github.com/zeno-98/NRTA_Learning

Active model learning is a crucial technique for automatically constructing formal models of black-box timed systems. However, existing learning approaches typically construct a single monolithic automaton for a timed system with multiple synchronous components, obscuring its component structure and hindering component-level analysis. We propose a compositional learning approach that constructs a deterministic real-time automaton (RTA) for each component with access only to the target system as a whole. Upon termination, the learned RTAs form a network that exhibits exactly the same timed behaviors as the target system. Within the respective resource limits, our implementation terminates successfully on 213 of the 240 (88.8%) randomly generated benchmark instances and all six adapted case-study benchmarks, and requires less learning time than monolithic approaches on some instances.

0.41

Agents as Software: A Programming Languages Agenda for Agent Reliability

cs.PL cs.AI ·2026-09-26 ·Shraddha Barke, Adithya Murali
published similarity 0.54
Abstract · Accepted to Onward! at SPLASH 2026

AI agents increasingly resemble software systems: they call tools, remember facts, follow policies, delegate work, and take actions with real consequences. % Yet the ``program'' of an agent is scattered across prompts, tools, memories, workflows, and execution traces, making its behavior difficult to inspect through ordinary testing and debugging alone. % This essay argues that a programming-systems perspective offers a natural lens for making agents reliable. % We recast agents as programmable artifacts whose behavior can be specified over traces and state, checked before deployment, monitored during execution, and improved from observed failures. % The goal is not to make probabilistic agents behave like deterministic programs, but to give them enough structure that their behavior can be reasoned about, controlled, and repaired.

0.27

MA-Mesh: Resilient Multi-Agent Collaboration via Role-based Self-Healing

cs.AI ·2026-11-04 ·JunYong Lee, Woo Kyung Kim, Honguk Woo
top venue similarity 0.54
Abstract · Accepted at EMNLP 2026 (Main)

Effective collaboration in multi-agent systems requires mechanisms for coordination and adaptability in dynamic and uncertain environments. However, existing multi-agent systems rarely model resilience explicitly, instead relying on ad-hoc output correction that limits systematic, runtime management of robustness. In this work, we propose Multi-Agent Mesh (MA-Mesh), a framework that constructs a role-based self-healing layer on top of a collaboration pattern. Specifically, MA-Mesh generates resilience-aware system specifications and synthesizes them into executable multi-agent policy code. To enhance resilience, we introduce two self-healing mechanisms: Cross-agent reflection, a mechanism that allows agents to evaluate not only their own outcomes but also the performance of their peers, enabling informed behavioral adjustments and collective policy refinement; Role-based failover, a strategy which dynamically reassigns roles and enables agents to substitute for one another when sub-tasks fail or agents underperform, ensuring continuity of task execution. Experimental results across diverse tasks (e.g., software development, tool use, scientific reasoning) demonstrate that MA-Mesh significantly outperforms existing multi-agent systems in both task performance and robustness under system uncertainty.

0.25

Pandora's Toolbox Or Why Agent Safety Cannot Be Verified

cs.AI ·2026-11-19 ·Mario Franco, Carlos Gershenson
similarity 0.53
Abstract

Present artificial intelligence agents are constructed by means of a coupling between a fixed language model with a general computing device. We show that this coupling makes safety undecidable. In particular, we show that given some dangerous program, no algorithm can predict whether an agent will run such a program that is semantically equivalent. In general, guardrails, blacklists, whitelists and certifications can only lead to imperfect safety solutions. Under finite constraints (bounded context, values and running time) safety is decidable but still intractable. Specifically, the problem is $\mathsf{PSPACE}$-complete even when the description of the agent is known. Finally, safety is not a compositional property, i.e., agents that can be proven safe on their own can still produce unsafe behavior when grouped together. We also discuss relaxed notions of safety that could be used in practice.

0.11

Synthesizing Update Schedules with Game-Based Extension of Bounded Model Checking

cs.GT cs.LO ·2026-09-28 ·Janis Kröger, Paul Kröger, Martin Fränzle
published similarity 0.52
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

Ensuring safe software updates in safety-critical systems without interrupting operation and without provisioning and activating cold spare hardware poses a fundamental challenge due to the conflict between system availability and update execution. In this paper, we present a bounded SMT encoding for synthesizing fixed global-time update schedules for timed-games with linear update automata and a fixed number of update transitions. We model the interaction between the system and the update as a two-player timed game. Our key contribution is the synthesis of global time points that define a fixed update schedule which guarantees safe and complete deployment of the update independently of the autonomous system behavior. To this end, we reduce the scheduling problem to a reachability and safety objective and encode it as a quantified SMT problem. We demonstrate it on an example system of a trajectory planner for autonomous driving, showing that the synthesized schedule ensures safe deployment under all admissible executions.

0.30