共查询到20条相似文献,搜索用时 31 毫秒
1.
Silvio Lago Pereira Leliane Nunes de Barros 《Autonomous Agents and Multi-Agent Systems》2008,16(3):327-344
Planning to reach a goal is an essential capability for rational agents. In general, a goal specifies a condition to be achieved
at the end of the plan execution. In this article, we introduce nondeterministic planning for extended reachability goals (i.e., goals that also specify a condition to be preserved during the plan execution). We show that, when this kind of goal is
considered, the temporal logic ctl turns out to be inadequate to formalize plan synthesis and plan validation algorithms. This is mainly due to the fact that
the ctl’s semantics cannot discern among the various actions that produce state transitions. To overcome this limitation, we propose
a new temporal logic called α-ctl. Then, based on this new logic, we implement a planner capable of synthesizing reliable plans for extended reachability goals,
as a side effect of model checking. 相似文献
2.
Hans L. Bodlaender Fedor V. Fomin Arie M. C. A. Koster Dieter Kratsch Dimitrios M. Thilikos 《Theory of Computing Systems》2012,50(3):420-432
In this note, we give a proof that several vertex ordering problems can be solved in O
∗(2
n
) time and O
∗(2
n
) space, or in O
∗(4
n
) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply. 相似文献
3.
This paper presents a distributed (Bulk-Synchronous Parallel or bsp) algorithm to compute on-the-fly whether a structured model of a security protocol satisfies a ctl \(^*\) formula. Using the structured nature of the security protocols allows us to design a simple method to distribute the state space under consideration in a need-driven fashion. Based on this distribution of the states, the algorithm for logical checking of a ltl formula can be simplified and optimised allowing, with few tricky modifications, the design of an efficient algorithm for ctl \(^*\) checking. Some prototype implementations have been developed, allowing to run benchmarks to investigate the parallel behaviour of our algorithms. 相似文献
4.
Compositional reasoning aims to improve scalability of verification tools by reducing the original verification task into
subproblems. The simplification is typically based on assume-guarantee reasoning principles, and requires user guidance to
identify appropriate assumptions for components. In this paper, we propose a fully automated approach to compositional reasoning
that consists of automated decomposition using a hypergraph partitioning algorithm for balanced clustering of variables, and
discovering assumptions using the L
* algorithm for active learning of regular languages. We present a symbolic implementation of the learning algorithm, and incorporate
it in the model checker NuSmv. In some cases, our experiments demonstrate significant savings in the computational requirements of symbolic model checking.
This research was partially supported by ARO grant DAAD19-01-1-0473, and NSF grants ITR/SY 0121431 and CCR0306382. 相似文献
5.
Alternating-time temporal logic (atl) is a logic for reasoning about open computational systems and multi-agent systems. It is well known that atl model checking is linear in the size of the model. We point out, however, that the size of an atl model is usually exponential in the number of agents. When the size of models is defined in terms of states and agents rather than transitions, it turns out that the problem is (1) Δ
3
P
-complete for concurrent game structures, and (2) Δ
2
P
-complete for alternating transition systems. Moreover, for “Positive atl” that allows for negation only on the level of propositions, model checking is (1) Σ
2
P
-complete for concurrent game structures, and (2) NP-complete for alternating transition systems. We show a nondeterministic polynomial reduction from checking arbitrary alternating
transition systems to checking turn-based transition systems, We also discuss the determinism assumption in alternating transition
systems, and show that it can be easily removed.
In the second part of the paper, we study the model checking complexity for formulae of atl
with imperfect information (atl
ir
). We show that the problem is Δ
2
P
-complete in the number of transitions and the length of the formula (thereby closing a gap in previous work of Schobbens
in Electron. Notes Theor. Comput. Sci. 85(2), 2004). Then, we take a closer look and use the same fine structure complexity measure as we did for atl with perfect information. We get the surprising result that checking formulae of atl
ir
is also Δ
3
P
-complete in the general case, and Σ
2
P
-complete for “Positive atl
ir
”. Thus, model checking agents’ abilities for both perfect and imperfect information systems belongs to the same complexity
class when a finer-grained analysis is used. 相似文献
6.
We consider concurrent probabilistic systems, based on probabilistic automata of Segala & Lynch [55], which allow non-deterministic
choice between probability distributions. These systems can be decomposed into a collection of “computation trees” which arise
by resolving the non-deterministic, but not probabilistic, choices. The presence of non-determinism means that certain liveness
properties cannot be established unless fairness is assumed. We introduce a probabilistic branching time logic PBTL, based on the logic TPCTL of Hansson [30] and the logic PCTL of [55], resp. pCTL [14]. The formulas of the logic express properties such as “every request is eventually granted with probability at least
p”. We give three interpretations for PBTL on concurrent probabilistic processes: the first is standard, while in the remaining two interpretations the branching time
quantifiers are taken to range over a certain kind of fair computation trees. We then present a model checking algorithm for
verifying whether a concurrent probabilistic process satisfies a PBTL formula assuming fairness constraints. We also propose adaptations of existing model checking algorithms for pCTL
[4, 14] to obtain procedures for PBTL
under fairness constraints. The techniques developed in this paper have applications in automatic verification of randomized
distributed systems.
Received: June 1997 / Accepted: May 1998 相似文献
7.
Model checking based on Petri net unfoldings is an approach widely applied to cope with the state space explosion problem. In this paper, we propose a new condensed representation of a Petri net’s behaviour called merged processes, which copes well not only with concurrency, but also with other sources of state space explosion, viz sequences of choices and non-safeness. Moreover, this representation is sufficiently similar to the traditional unfoldings, so that a large body of results developed for the latter can be re-used. Experimental results indicate that the proposed representation of a Petri net’s behaviour alleviates the state space explosion problem to a significant degree and is suitable for model checking.V. Khomenko is a Royal Academy of Engineering/Epsrc Research Fellow supported by the RAEng/Epsrc grant EP/C53400X/1 (Davac).M. Koutny is supported by the EC IST grant 511599 (Rodin).W. Vogler is supported by the DFG-project STG-Dekomposition VO 615/7-1 相似文献
8.
Saswat Anand Corina S. Păsăreanu Willem Visser 《International Journal on Software Tools for Technology Transfer (STTT)》2009,11(1):53-67
We address the problem of error detection for programs that take recursive data structures and arrays as input. Previously
we proposed a combination of symbolic execution and model checking for the analysis of such programs: we put a bound on the size of the program inputs and/or the search depth of the model checker to limit the search state space. Here we look
beyond bounded model checking and consider state matching techniques to limit the state space. We describe a method for examining
whether a symbolic state that arises during symbolic execution is subsumed by another symbolic state. Since the number of symbolic states may be infinite, subsumption is not enough to ensure termination.
Therefore, we also consider abstraction techniques for computing and storing abstract states during symbolic execution. Subsumption
checking determines whether an abstract state is being revisited, in which case the model checker backtracks—this enables
analysis of an under-approximation of the program behaviors. We illustrate the technique with abstractions for lists and arrays. We also discuss abstractions
for more general data structures. The abstractions encode both the shape of the program heap and the constraints on numeric
data. We have implemented the techniques in the Java PathFinder tool and we show their effectiveness on Java programs. This
paper is an extended version of Anand et al. (Proceedings of SPIN, pp. 163–181, 2006). 相似文献
9.
We investigate a class of parametric timed automata, called lower bound/upper bound (L/U) automata, where each parameter occurs
in the timing constraints either as a lower bound or as an upper bound. For such automata, we show that basic decision problems,
such as emptiness, finiteness and universality of the set of parameter valuations for which there is a corresponding infinite
accepting run of the automaton, is Pspace-complete. We extend these results by allowing the specification of constraints on parameters as a linear system. We show
that the considered decision problems are still Pspace-complete, if the lower bound parameters are not compared with the upper bound parameters in the linear system, and are undecidable
in general. Finally, we consider a parametric extension of
MITL\mathsf{MITL}
0,∞, and prove that the related satisfiability and model checking (w.r.t. L/U automata) problems are Pspace-complete. 相似文献
10.
Roberto Sebastiani Eli Singerman Stefano Tonetta Moshe Y. Vardi 《Formal Methods in System Design》2007,31(2):177-196
Verifying whether an ω-regular property is satisfied by a finite-state system is a core problem in model checking. Standard techniques build an
automaton with the complementary language, compute its product with the system, and then check for emptiness. Generalized
symbolic trajectory evaluation (GSTE) has been recently proposed as an alternative approach, extending the computationally
efficient symbolic trajectory evaluation (STE) to general ω-regular properties. In this paper, we show that the GSTE algorithms are essentially a partitioned version of standard symbolic
model-checking (SMC) algorithms, where the partitioning is driven by the property under verification. We export this technique
of property-driven partitioning to SMC and show that it typically does speed up SMC algorithms.
A shorter version of this paper has been presented at CAV’04 (R. Sebastiani et al., Lecture Notes in Comput. Sci., vol. 3114,
pp. 143–160, 2004).
R. Sebastiani supported in part by the CALCULEMUS! IHP-RTN EC project, code HPRN-CT-2000-00102, by a MIUR COFIN02 project, code 2002097822_003, and by a grant from the Intel Corporation.
M.Y. Vardi supported in part by NSF grants CCR-9988322, CCR-0124077, CCR-0311326, IIS-9908435, IIS-9978135, EIA-0086264, and
ANI-0216467 by BSF grant 9800096, and by a grant from the Intel Corporation. 相似文献
11.
We show how LTL model checking can be reduced to CTL model checking with fairness constraints. Using this reduction, we also describe how to construct a symbolic LTL model checker that appears to be quite efficient in practice. In particular, we show how the SMV model checking system developed by McMillan [16] can be extended to permit LTL specifications. The results that we have obtained are quite surprising. For the specifications which can be expressed in both CTL and LTL, the LTL model checker required at most twice as much time and space as the CTL model checker. We also succeeded in verifying non-trivial LTL specifications. The amount of time and space that is required is quite reasonable. Based on the examples that we considered, it appears that efficient LTL model checking is possible when the specifications are not excessively complicated. 相似文献
12.
《Science of Computer Programming》1987,8(3):275-306
We consider automatic verification of finite state concurrent programs. The global state graph of such a program can be viewed as a finite (Kripke) structure, and amodel checking algorithm can be given for determining if a given structure is a model of a specification expressed in a propositional temporal logic. In this paper, we present a unified approach for efficient model checking under a broad class of generalized fairness constraints in a branching time framework extending that of Clarke et al. (1983). Our method applies to any type of fairness expressed in a certain canonical form. Almost all ‘practical’ types of fairness from the literature, including the fundamental notions of impartiality, weak fairness, and strong fairness, can be succintly written in our canonical form. Moreover, our branching time approach can easily be adapted to handle types of fairness (such as fair reachability of a predicate) which cannot even be expressed in a linear temporal logic. We go on to argue that branching time logic is always better than linear time logic for model checking. We show that given any model checking algorithm for any system of linear time logic (in particular, for the usual system of linear time logic) there is a model checking algorithm of the same order of complexity (in both the structure and formula size) for the corresponding full branching time logic which trivially subsumes the linear time logic in expressive power (in particular, for the system of full branching time logic CTL*). We also consider an application of our work to the theory of finite automata on infinite strings. 相似文献
13.
This paper gives poly-logarithmic-round, distributed δ-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio δ is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with δ = 2). Via duality, the paper also gives poly-logarithmic-round, distributed δ-approximation algorithms for Fractional Packing linear programs (where δ is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where δ is the maximum size of any of the hyperedges; for graphs δ = 2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms. 相似文献
14.
Liveness temporal properties state that something “good” eventually happens, e.g., every request is eventually granted. In
Linear Temporal Logic (LTL), there is no a priori bound on the “wait time” for an eventuality to be fulfilled. That is, F
θ asserts that θ holds eventually, but there is no bound on the time when θ will hold. This is troubling, as designers tend to interpret an eventuality F
θ as an abstraction of a bounded eventuality F
≤k
θ, for an unknown k, and satisfaction of a liveness property is often not acceptable unless we can bound its wait time. We introduce here prompt-LTL, an extension of LTL with the prompt-eventually operator F
p
. A system S satisfies a prompt-LTL formula φ if there is some bound k on the wait time for all prompt-eventually subformulas of φ in all computations of S. We study various problems related to prompt-LTL, including realizability, model checking, and assume-guarantee model checking, and show that they can be solved by techniques
that are quite close to the standard techniques for LTL. 相似文献
15.
Sagar Chaki Edmund Clarke Natasha Sharygina Nishant Sinha 《Formal Methods in System Design》2008,32(3):235-266
This paper presents an automated and compositional procedure to solve the substitutability problem in the context of evolving software systems. Our solution contributes two
techniques for checking correctness of software upgrades: (1) a technique based on simultaneous use of over-and under-approximations
obtained via existential and universal abstractions; (2) a dynamic assume-guarantee reasoning algorithm—previously generated component assumptions are reused and altered on-the-fly to prove
or disprove the global safety properties on the updated system. When upgrades are found to be non-substitutable, our solution
generates constructive feedback to developers showing how to improve the components. The substitutability approach has been
implemented and validated in the ComFoRT reasoning framework, and we report encouraging results on an industrial benchmark.
This is an extended version of a paper, Dynamic Component Substitutability Analysis, published in the Proceedings of the Formal Methods 2005 Conference, Lecture Notes in Computer Science, vol. 3582, by the
same authors. This research was sponsored by the National Science Foundation under grant nos. CNS-0411152, CCF-0429120, CCR-0121547,
and CCR-0098072, the Semiconductor Research Corporation under grant no. TJ-1366, the US Army Research Office under grant no.
DAAD19-01-1-0485, the Office of Naval Research under grant no. N00014-01-1-0796, the ICAST project and the Predictable Assembly
from Certifiable Components (PACC) initiative at the Software Engineering Institute, Carnegie Mellon University. The views
and conclusions contained in this document are those of the authors and should not be interpreted as representing the official
policies, either expressed or implied, of any sponsoring institution, the US government or any other entity. 相似文献
16.
Model checking is a useful method to verify automatically the correctness of a system with respect to a desired behavior, by checking whether
a mathematical model of the system satisfies a formal specification of this behavior. Many systems of interest are open, in
the sense that their behavior depends on the interaction with their environment. The model checking problem for finite-state
open systems (called module checking) has been intensively studied in the literature. In this paper, we focus on open pushdown systems and we study the related model-checking problem (pushdown module checking, for short) with respect to properties expressed by CTL and CTL
* formulas. We show that pushdown module checking against CTL (resp., CTL
*) is 2Exptime-complete (resp., 3Exptime-complete). Moreover, we prove that for a fixed CTL or CTL
* formula, the problem is Exptime-complete. 相似文献
17.
There is a great deal of research aimed toward the development of temporal logics and model checking algorithms which can be used to verify properties of systems. In this paper, we present a methodology and supporting tools which allow researchers and practitioners to automatically generate model checking algorithms for temporal logics from algebraic specifications. These tools are extensions of algebraic compiler generation tools and are used to specify model checkers as mappings of the form
, where L
s is a temporal logic source language and L
t is a target language representing sets of states of a model M, such that
. The algebraic specifications for a model checker define the logic source language, the target language representing sets of states in a model, and the embedding of the source language into the target language. Since users can modify and extend existing specifications or write original specifications, new model checking algorithms for new temporal logics can be easily and quickly developed; this allows the user more time to experiment with the logic and its model checking algorithm instead of developing its implementation. Here we show how this algebraic framework can be used to specify model checking algorithms for CTL, a real-time CTL, CTL*, and a custom extension called CTL
e that makes use of propositions labeling the edges as well as the nodes of a model. We also show how the target language can be changed to a language of binary decision diagrams to generate symbolic model checkers from algebraic specifications. 相似文献
18.
Paolo Terenziani 《Computational Intelligence》2000,16(2):210-256
In many areas of Computer Science, including planning, workflows, guidelines, and protocol management, one has to deal with abstract plans, procedures, or schedules involving temporal constraints between classes of actions that have to be repeated at periodic times and may be instantiated in different ways for different executions of the plans (procedures, schedules). In this paper we propose an integrated framework to deal with both qualitative temporal constraints on classes of actions and temporal constraints between instances of actions, in which temporal reasoning is used to amalgamate both types of constraints and to check their consistency. In particular, we consider an expressive formalism to deal with temporal constraints between classes of actions (with special attention to periodic actions) which takes into account different components such as frame times, numeric quantification, periods, and qualitative relations. We define the notions of (contextual) concretization of qualitative temporal constraints between classes and use this notion to formally define the consistency of a knowledge base of temporal constraints between classes and a set of temporal constraints on instances, and to define the algorithm for checking such a consistency. An application for scheduling lessons in a school is shown in an example. 相似文献
19.
In this paper, we undertake the competitive analysis of the online real-time scheduling problems under a given hard energy
constraint. Specifically, we derive worst-case performance bounds that apply to any online algorithm, when compared to an
optimal algorithm that has the knowledge of the input sequence in advance. First, by focusing on uniform value-density settings,
we prove that no online algorithm can achieve a competitive factor greater than
1-\fracemaxE1-\frac{e_{\max}}{E}, where e
max is the upper bound on the size of any job and E is the available energy budget. Then we propose a variant of EDF algorithm, EC-EDF, that is able to achieve this upper bound. We show that a priori information about the largest job size in the actual input sequence makes possible the design of a semi-online algorithm
EC-EDF
∗ which achieves a constant competitive factor of 0.5. This turns out to be the best achievable competitive factor in these
settings. In non-uniform value density settings, we derive an upper bound on the competitive factor achievable by any online
algorithm, as well as the competitive factors of EC-EDF and EC-EDF
∗ algorithms. We also investigate the implications of having additional constraints on the online scheduling algorithm, including
non-idling and non-preemptive execution constraints. Moreover, we analyze the case where the processor can adjust its speed at run-time through Dynamic
Voltage Scaling (DVS) capability. 相似文献
20.
由于经典的线性时序逻辑表达能力有限,设计并开发了基于交替投影时序逻辑(alternating projection temporal logic,简称APTL)的模型检测工具.根据王海洋等人提出的APTL符号模型检测方法,设计并实现了APTL模型检测器MCMAS_APTL.该工具可用于多智能体系统(multi-agent system,简称MAS)的性质验证.MCMAS_APTL检查MAS是否满足具体性质的过程如下:首先,用解释系统编程语言(interpreted system programming language,简称ISPL)描述要验证的系统IS,用APTL公式P描述要验证的性质;然后,符号化表示系统IS,并将非P转化为范式;最后,计算所有满足非P的路径的起始状态集合.如果得到的状态集合中包含系统的初始状态,则说明系统不满足公式P;反之,则说明系统满足公式P.详细阐述了实现MCMAS_APTL的过程,并且通过验证机器人足球赛的例子展示了MCMAS_APTL的性能. 相似文献