اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدModule checking of pushdown multi-agent systems
86
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we investigate the module-checking problem of pushdown multi-agent systems (PMS) against ATL and ATL* specifications. We establish that for ATL, module checking of PMS is 2EXPTIME-complete, which is the same complexity as pushdown module-checking for CTL. On the other hand, we show that ATL* module-checking of PMS turns out to be 4EXPTIME-complete, hence exponentially harder than both CTL* pushdown module-checking and ATL* model-checking of PMS. Our result for ATL* provides a rare example of a natural decision problem that is elementary yet but with a complexity that is higher than triply exponential-time.
قيم البحث
اقرأ أيضاً
In this paper, we settle a problem in probabilistic verification of infinite--state process (specifically, {it probabilistic pushdown process}). We show that model checking {it stateless probabilistic pushdown process} (pBPA) against {it probabilistic computational tree logic} (PCTL) is undecidable.
This volume contains the proceedings of the First Workshop on Logics and Model-checking for self-* systems (MOD* 2014). The worshop took place in Bertinoro, Italy, on 12th of September 2014, and was a satellite event of iFM 2014 (the 11th Internation
al Conference on Integrated Formal Methods). The workshop focuses on demonstrating the applicability of Formal Methods on modern complex systems with a high degree of self-adaptivity and reconfigurability, by bringing together researchers and practitioners with the goal of pushing forward the state of the art on logics and model checking.
This paper is about reachability analysis in a restricted subclass of multi-pushdown automata. We assume that the control states of an automaton are partially ordered, and all transitions of an automaton go downwards with respect to the order. We pro
ve decidability of the reachability problem, and computability of the backward reachability set. As the main contribution, we identify relevant subclasses where the reachability problem becomes NP-complete. This matches the complexity of the same problem for communication-free vector addition systems, a special case of stateless multi-pushdown automata.
In this report we focus on some aspects related to modeling and formal verification of embedded systems. Many models have been proposed to represent embedded systems. These models encompass a broad range of styles, characteristics, and application do
mains and include the extensions of finite state machines, data flow graphs, communication processes and Petri nets. In this report, we have used a PRES+ model (Petri net based Representation for Embedded Systems) as an extension of classical Petri net model that captures concurrency, timing behaviour of embedded systems; it allows systems to be representative in different levels of abstraction and improves expressiveness by allowing the token to carry information. Modeling using PRES+, as discussed above, may be convenient for specifying the input behaviour because it supports concurrency. However, there is no equivalence checking method reported in the literature for PRES+ models to the best of our knowledge. In contrast, equivalence checking of FSMD models exist. As a first step, therefore, we seek to devise an algorithm to translate PRES+ models to FSMD models.
This paper studies the logical properties of a very general class of infinite ranked trees, namely those generated by higher-order recursion schemes. We consider, for both monadic second-order logic and modal mu-calculus, three main problems: model-c
hecking, logical reflection (aka global model-checking, that asks for a finite description of the set of elements for which a formula holds) and selection (that asks, if exists, for some finite description of a set of elements for which an MSO formula with a second-order free variable holds). For each of these problems we provide an effective solution. This is obtained thanks to a known connection between higher-order recursion schemes and collapsible pushdown automata and on previous work regarding parity games played on transition graphs of collapsible pushdown automata.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
