Verification of time-bounded multiset rewriting properties

Read full text Summarise with VIRAT
Authors: Tajana Ban Kirigin, Jesse Comer, Max Kanovich, Andre Scedrov, Carolyn Talcott
Cited by: 0
References: 48

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

We analyze the computational complexity of several time-bounded verification problems for timed multiset rewriting systems, including reachability, safety, realizability , and survivability . Our study culminates with a complexity analysis of a novel notion of time-bounded resilience . This latter notion addresses a significant gap in the literature on system design, which has focused on optimizing efficiency , while giving insufficient attention to the design of resilient systems - systems able to adapt to unexpected or even adversarial disruptions. We show that, in the time-bounded model with n (adversarially-chosen) disruptions, the corresponding time-bounded resilience problem for the class of η-simple, progressing systems is complete for the Σ 2 n + 1 P class of the polynomial hierarchy, PH . To complement our theoretical work, we perform an automated analysis of time-bounded resilience using the rewriting logic tool Maude.

Fields of Study & Subjects

Formal Methods in Verification Logic programming and type systems Petri Nets in System Modeling

Publication details

Journal / source
Journal of Logical and Algebraic Methods in Programming
Volume
150
Pages
101124–101124
Publication date
22 March 2026
Language
EN