CS Paper Radar

Daily listing

2026-11-17 · cs.LO

13 papers first submitted this day (UTC) in cs.LO — Logic in Computer Science. arXiv announces a day's submissions the next evening, so the newest day fills up over ~24 h.

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works

AI & Machine Learning 1

ROSMonitoring in Action: Runtime Monitoring and Enforcement for ROS 2 Actions

cs.AI cs.LOcs.RO ·2026-11-17 ·Giacomo Paltrinieri, Angelo Ferrando
published
Abstract · In Proceedings FMAS 2026, arXiv:2611.21375

Robotic applications often rely on long-running operations, such as navigation, manipulation, and inspection, which in ROS~2 are commonly implemented as actions. Unlike topics and services, actions involve a structured lifecycle comprising goal submission and acceptance, feedback, status updates, result retrieval, and cancellation. Existing versions of ROSMonitoring support topics and services, but do not reconstruct this lifecycle or expose action-level events to a runtime-verification oracle. In this paper, we extend ROSMonitoring with runtime monitoring and enforcement for ROS~2 actions. Actions are declared directly in the monitoring configuration and automatically instrumented through the underlying ROS~2 communication endpoints. The generated monitor reconstructs action-level events, correlates them through goal identifiers, maintains the state of active goals, and translates violations into protocol-aware enforcement operations. These include goal rejection, cancellation, message suppression, and protocol-compliant responses generated directly by the monitor when the original communication cannot be forwarded. We evaluate the implementation through controlled stress tests that vary the number of action invocations, workload size, and client–server topology. The results show approximately linear growth in monitoring cost with repeated action invocations under a fixed workload, while larger action workloads and a greater number of configured client–server pairs introduce additional overhead. These results characterise the scaling behaviour of the current implementation under the tested sequential workloads while highlighting the main performance limitations of the current synchronous implementation.

0.29

Security & Privacy 1

From Attack Tree to Model Checker: Binding CAPEC Patterns to Verify Robotic System Security

cs.CR cs.LO ·2026-11-17 ·Juel Hussain, Louise A. Dennis, Clare Dixon, Marie Farrell
published
Abstract · In Proceedings FMAS 2026, arXiv:2611.21375

Security-minded verification of autonomous and robotic systems presupposes an attacker, yet the path from a threat catalogue to a checkable attacker model is still traversed by hand. This research preview presents the theory and construction of a pipeline that mechanises it. Each leaf of an attack tree is mapped to a CAPEC attack pattern and written in first-order logic as a rule: the attacker's prerequisites imply the attack's effect. Casting the pattern as such a rule is what makes it operational - its variables can be bound to a specific system's parts, and its prerequisites can then be tested against that system under a chosen configuration of security controls. Binding is our means of verifying whether a system is vulnerable to a given attack: from a bound pattern we derive an attacker model, turn its effect into a temporal-logic property, and check that property against the system with and without a countermeasure, reporting the control that defeats the attack. We describe the signature, schemas, profiles for approach, and explore how CAPEC can support reasoning about robotics security.

0.67

Software & Programming 9

BehaVerify: A Formal Verification Tool for Behavior Trees

cs.SE cs.LOcs.RO ·2026-11-17 ·Serena S. Serbinowska, Ben Wooding, Diego Manzanas Lopez, Luke Nam, Anne M. Tumlin +3 more
publishedcode/datahot direction
Abstract · In Proceedings FMAS 2026, arXiv:2611.21375

This paper presents BehaVerify, a verification toolbox for behavior trees (BTs) and Neuro-Symbolic BTs. BTs are a graphical language for planning and sequencing behaviors - similar to extended state machines - and are increasingly used in safety-critical domains. BehaVerify enables users to specify a BT using a Domain Specific Language (DSL) with formal syntax and semantics. This language further includes Linear Temporal Logic and Computation Tree Logic specifications. BehaVerify uses an efficient encoding into nuXmv, called fastforwarding, to quickly verify if a specification holds over the BT. Additionally, BehaVerify can generate implementations of the BT in Python and Haskell. Through Python, BehaVerify has been integrated with PyTrees and Robot Operating System (ROS) and has been deployed to several autonomous robotic systems, including for verifying runtime monitors. While prior works have developed the underlying theory, this manuscript focuses on the toolbox usage, functionality and implementation. BehaVerify is open source: https://github.com/verivital/behaverify

0.73

From Constraints to Causality: Petri net Encodings for Explaining Binary Neural Network Inference

cs.LO cs.LG ·2026-11-17 ·Alex Chan, Mohamed Tarraf, Alex Yakovlev, Rishad Shafik
publishedtheory
Abstract · In Proceedings FMAS 2026, arXiv:2611.21375

Binary Neural Networks (BNNs) are attractive for resource-constrained hardware and on-device components in autonomous systems. However, their discrete, non-linear behaviour makes them difficult to analyse and trust in safety-relevant settings. Existing approaches based on SAT and Satisfiability Modulo Theories can verify a BNN's input-output properties, but treat it as a monolithic constraint system, which reveal only whether a property holds and not how the computation reaches its result. In this paper, we present an early work that provides a complementary, discrete-event view. We give a compositional translation from the inference semantics of a fixed, trained BNN to a 1-safe Petri net (PN), where each computation step is an explicit transition, so that a firing sequence is a causal trace of the BNN's decision. On a worked example, we establish faithfulness via exhaustive input-output equivalence against a reference implementation, and show how contrasting firing sequences localises where a single-feature change alters the prediction. Finally, we outline two directions this opens: a correctness-of-translation theorem, and a causal-trace analysis of where two trained BNNs diverge in their decisions, a structural question that constraint-based verifiers cannot express.

0.65

Plenty to FRET About: From Hazard Analysis to Formal Requirements for Robot-Assisted Dressing

cs.LO cs.HCcs.RO ·2026-11-17 ·Gunjari Chakraborty, Yasmin Rafiq, Hazel M. Taylor, Marie Farrell
published
Abstract · In Proceedings FMAS 2026, arXiv:2611.21375

Understanding requirements for systems involving humans and robots is essential for providing robust evidence that such systems behave correctly. Requirements formalisation approaches such as the Formal Requirements Elicitation Tool (FRET) can support the transition from unstructured natural language to formal representations suitable for verification. In this paper, we formalise 146 hazard-derived natural-language requirements for a Robot-Assisted Dressing (RAD) case study, previously classified using a taxonomy of Human-Robot Teamwork (HRT) requirements. Through an iterative process involving domain-expert clarification, these were represented by 117 unique FRETISH requirements. Formalisation exposed ambiguities, temporal and probabilistic assumptions, and cases where source requirements needed to be decomposed or could be consolidated because they expressed the same formal behaviour. Temporal analysis showed that 70.1% of the unique FRETISH requirements use either immediate-response or ordering constraints (immediately or before), while formalisation also exposed relationships between requirements across HRT taxonomy categories. We further analyse the formal semantics and realisability of the resulting requirements. The results show that HRT classification and formalisation provide complementary views: the taxonomy captures the teamwork concern represented by a requirement, while FRETISH makes the required behaviour explicit. We report practical lessons and limitations of applying FRET to HRT requirements and identify directions for further work.

0.60

Let's Talk This Out: Towards Explanation-based Distributed Goal Satisfaction

cs.LO ·2026-11-17 ·Anton Reinecke, Sibylle Schupp
published
Abstract · In Proceedings FMAS 2026, arXiv:2611.21375

Digital systems are embedded in a modular environment of different components with individual goals and settings, which are often installed without central oversight. In this research preview paper we present a framework for communication between components to facilitate compositional problem solving based on explanation patterns and A/G-contracts, without the need for an oracle. Our approach uses partial MaxSMT solving and quantifier elimination to compute counterfactual explanation messages. We illustrate the feasibility of the approach with a proof-of-concept chain topology example, and discuss future challenges when expanding the protocol to more complex topologies.

0.58

RyBench: Runtime Verification Benchmarking Framework over Publish/Subscribe Networks

cs.LO cs.PFcs.SE ·2026-11-17 ·Mehmet Hilmi Dündar, Doğan Ulus
publishedbenchmark
Abstract · In Proceedings FMAS 2026, arXiv:2611.21375

Autonomous systems built as distributed, node-based systems communicate via publish/subscribe middleware. Runtime Verification (RV) tools are used to monitor those systems against formal specifications, receiving monitored events through the pub/sub channel. An RV tool's practical value depends on its monitoring throughput capacity and verdict latency, besides its correctness, so a systematic benchmarking setup is needed to evaluate how efficiently these tools run. This paper presents RyBench, a pub/sub-based benchmarking framework that acts as a synthetic event publisher in place of a monitored system, providing a common benchmarking setup. RyBench separates benchmark generation, serialization, and transport into distinct components, enabling the combination of different event-generation strategies, data formats, and transport layers. We also evaluate the framework's throughput capacity across these configurations using Open Simulation Interface (OSI) schemas and Timescales properties, and illustrate the end-to-end benchmarking flow through an application to Reelay and an integration with MonPoly.

0.51

Python Code Generation for Isabelle/HOL

cs.PL cs.LOcs.SE ·2026-11-17 ·Nikolaus Huber, Roly Perera, Dominic Orchard
theory
Abstract · 20 pages, 19 figures, 2 tables. Software artefact: https://doi.org/10.5281/zenodo.24106993

The Isabelle theorem prover provides an environment for formalising mathematics and reasoning about programs. To make verified implementations practically usable, its code generator translates functions expressed in the executable fragment of its logic into conventional programming languages. Its targets have traditionally been functional languages (Standard ML, OCaml, Haskell, and Scala), recently joined by Go. Python, which is becoming the dominant language of scientific computing, data science, and education, has remained out of reach. In this work, we close this gap with a Python backend for Isabelle's code generator. This generator enables verified algorithms to be used in Python applications, or to serve as verified references against which established Python libraries can be differentially tested, without leaving the Python ecosystem. We validate the backend on regression suites covering large parts of the HOL library and by testing six verified data structures and algorithms against established Python libraries. The generated code is slower than hand-written libraries, but well suited as a verified reference.

0.48

Probabilistic Simple Types for Almost-Sure Termination (Extended Version)

cs.LO ·2026-11-17 ·Ugo Dal Lago, Willem Heijltjes
Abstract · Extended version of the published paper at CSL 2027

We present a type system for almost-sure termination (AST) in higher-order probabilistic computation. Our vehicle is the recent Functional Machine Calculus (FMC), which combines the lambda-calculus with effectful imperative computation. Importantly for our purpose, it models branching and looping computation with sum types and a typed iterator construct. Our key observation is that by replacing sum types with probability distributions, types ensure that iteration has a non-zero chance of exiting, which then gives AST in a simple and natural way. Concretely, our type system assigns explicit probability distributions to termination outcomes, allowing probabilistic behaviour to be tracked compositionally at the type level. Types then soundly guarantee almost-sure termination, even in the presence of higher-order functions. The fragment of ground terms, which consists purely of the branching and iteration constructs with probabilistic sampling, is equivalent to finite Markov chains and is positively AST (expected evaluation time is finite). The full calculus is more expressive, which we demonstrate through an example term with infinite expected evaluation time.

0.40

A Unifying Metatheorem on Weak-Memory Robustness

cs.PL cs.LO ·2026-11-17 ·Giovanna Kobus Conrado, Stephan Spengler, Mohamed Faouzi Atig, Andreas Pavlogiannis
theory
Abstract

Memory models specify the behaviors that concurrent programs may exhibit under compiler and hardware optimizations, which often deviate from Sequential Consistency (SC). Robustness is the property of a program P not exhibiting any weak behaviors when executing under a weak memory model MM, compared to SC. As such, the algorithmic problem of deciding whether $P$ is robust against MM has been studied extensively, and has been repeatedly shown to be in PSPACE for many memory models, such as TSO, PSO, and Release/Acquire. However, each model has required its own, dedicated proof, raising the natural question of whether robustness admits a unifying treatment across memory models. In this work, we answer this question affirmatively for a broad class of memory models definable in Kleene Algebra with Tests (KAT). We prove that robustness against any prefix-closed, KAT-definable memory model is in PSPACE. This metatheorem recovers nearly all prior PSPACE robustness results, and establishes PSPACE membership for several new models, including the full RC11 and the OCaml memory model. We have further formalized the correctness of our approach in Lean. On the other hand, we prove that robustness against the KAT-definable Relaxed model is undecidable, and thus prefix-closedness cannot be dropped, in general. Finally, we implement our algorithm in a prototype tool RoboKAT, and demonstrate its flexibility by checking robustness against nine memory models, several of which are not handled by prior work.

0.35

Path Abstraction for Markov Reward Models: An Isabelle Formalisation in a Free Monoid View

cs.LO cs.FL ·2026-11-17 ·Arnd Hartmanns, Robert Modderman
Abstract

The classical definition of discrete-time Markov chains maps pairs of states to transition probabilities. An alternative, proposed in the context of path abstraction in probabilistic counterexample refinement, is to view them as a transition kernel on the free monoid on the state space, mapping paths directly to path probabilities. In this paper, we first extend the free monoid view and path abstraction algorithm to cumulative rewards on Markov reward models. We then use Isabelle/HOL to formalise Markov chains and reward models in this view, exploiting the discrete finite-prefix semantics to work with Isabelle's standard HOL-Analysis library. We mechanise the path abstraction algorithm and its key correctness properties of well-definedness and monotonic absorption, establishing the preservation of reachability probabilities and expected rewards. Proving the convergence of these quantities on relevant path sets is aided by our use of the lightweight free monoid semantics in place of the standard measure-theoretic one used in established Isabelle formalisations of Markov models. We obtain a verified abstract implementation of path abstraction in Isabelle/HOL, providing a foundation for refinement to efficient executable code and integration with probabilistic model checkers.

0.21

Theory & Algorithms 1

Entanglement Lower Bounds for Symmetric Quantum Circuits

cs.CC quant-phcs.LO ·2026-11-17 ·Davi Castro-Silva, Ryan Dancy, Sergii Strelchuk
theory
Abstract

Symmetric circuits require every symmetry of the input to extend to an automorphism of the circuit. In the classical setting, their connection to descriptive complexity yields strong unconditional lower bounds. We extend this approach to the quantum model of symmetric computation defined by Castro-Silva, Gur, and Strelchuk (ITCS 2026), proving a tradeoff between circuit size and entanglement width (the smallest $b$ such that, on every computational-basis input, the state after each layer factors into states on at most $b$ qubits each). Our main result identifies a graph property decidable in classical polynomial time that no polynomial-size family of symmetric quantum circuits on $n$-vertex graphs with entanglement width $o(n/\log n)$ can compute. The bound holds for circuits with arbitrary one-qubit and two-qubit gates and unrestricted depth, and remains valid under the weaker notion of symmetry with respect to even permutations of vertices. Our proof is based on a new quantum pebble game based on the partial trace. The resulting indistinguishability theorem transfers classical pebble-game lower bounds to quantum circuits with restricted entanglement. By contrast, without entanglement restrictions, we show that every graph property in BQP can be computed by a uniform family of polynomial-size symmetric quantum circuits. Restricting to circuits with no entanglement at all, we show that polynomial-size symmetric quantum circuits with entanglement width 1 can compute every graph property definable in fixed-point logic with counting. Finally, we give an efficient symmetric implementation of QAOA for MAX 3XOR, providing a starting point for studying entanglement lower bounds in quantum optimization algorithms.

0.34

Robotics, Control & Signals 1

SkiNet-Sim: Simulating Petri Nets with Data for the Verification and Validation of Controllers for Autonomous Systems

cs.RO cs.LOcs.PL ·2026-11-17 ·Baptiste Pelletier, Karen Godary
published
Abstract · In Proceedings FMAS 2026, arXiv:2611.21375

A large amount of high-level Petri net formalisms has been investigated and deployed in academic settings over the past decades, but these deployments fail to reach practical applications, despite the strong guarantees they can bring to stakeholders. In particular, the lack of direct benefits from end-users reduces the appeal of Petri nets, both due to the overly simple classical Petri net formalism, and the overly specialized high-level formalisms, on top of state-space explosion issues. In this work, we investigate how a middle-ground could be reached, by separating the implementation-specific aspects of software or hardware behaviors, from the classical Petri net semantics. The goal is to benefit from the sought-after aspects of Petri nets, namely their simple firing semantic and model-checking capabilities, while still being able to augment their behavior to best reflect the modelled system. We present a formal model of Interpreted Petri nets with data-aware transitions and tokens. We illustrate this formalism by modelling the executive layer of a robotic system, and provide a lightweight tool to augment classical Petri nets for general purpose applications, as well as data-aware state-space exploration for model-checking. Their specialization in the context of autonomous robotics is showcased, with a complete industrial inspection mission use-case, to compare simulation and model-checking results between the classical and the new data-aware Petri net semantic.

0.52