Search

We develop an algorithm to compute timed reachability probabilities for distributed models which are both probabilistic and nondeterministic. To obtain realistic results we consider the recently introduced class of (strongly) distributed schedulers, for which no analysis techniques are known. Our algorithm is based on reformulating the nondeterministic models as parametric ones, by interpreting scheduler decisions as parameters. We then apply the PARAM tool to extract the reachability probability as a polynomial function, which we optimize using nonlinear programming. [ABSTRACT FROM AUTHOR]

This paper presents a novel technique for counterexample generation in probabilistic model checking of Markov chains and Markov Decision Processes. (Finite) paths in counterexamples are grouped together in witnesses that are likely to provide similar debugging information to the user. We list five properties that witnesses should satisfy in order to be useful as debugging aid: similarity, accuracy, originality, significance, and finiteness. Our witnesses contain paths that behave similarly outside strongly connected components. Then, we show how to compute these witnesses by reducing the problem of generating counterexamples for general properties over Markov Decision Processes, in several steps, to the easy problem of generating counterexamples for reachability properties over acyclic Markov chains. [ABSTRACT FROM AUTHOR]

This paper presents an integrated GIS and cellular automata (CA) modelling and simulation environment. We hold that several concurrent facts offer the necessary critical mass to foster the development of robust and scalable general-purpose CA-modelling tools that go beyond demonstrative proof-of-concept status, allowing thus fully operational modelling and simulation of real-world territorial systems. Among these facts, we can mention the entering of the CA-based geosimulation modelling in its age of maturity, the growing computational capabilities of nowadays computers, the consolidation of general-purpose as well as specialised GIS-based geo-analysis methodologies and their availability as open-source libraries and applications. The environment hereby described is an example of a way to obtain such robust and general-purpose CA-modelling tool-box. Its main characteristics are (1) tight interoperability between GIS and CAs, (2) a sufficiently generalised and flexible underlying CA meta-model allowing for the implementation of a variety of types of CA models, (3) computationally efficiency and (4) user-friendliness. We furthermore present two test case applications to illustrate a standard operational modelling workflow within this simulation environment and to briefly illustrate its look-and-feel. [ABSTRACT FROM AUTHOR]

The technique of partial order reduction (POR) for probabilistic model checking prunes the state space of the model so that a maximizing scheduler and a minimizing one persist in the reduced system. This technique extends Peled΄s original restrictions with a new one specially tailored to deal with probabilities. It has been argued that not all schedulers provide appropriate resolutions of nondeterminism and they yield overly safe answers on systems of distributed nature or that partially hide information. In this setting, maximum and minimum probabilities are obtained considering only the subset of so-called distributed or partial information schedulers. In this article we revise the technique of partial order reduction (POR) for LTL properties applied to probabilistic model checking. Our reduction ensures that distributed schedulers are preserved. We focus on two classes of distributed schedulers and show that Peled΄s restrictions are valid whenever schedulers use only local information. We show experimental results in which the elimination of the extra restriction leads to significant improvements. [ABSTRACT FROM AUTHOR]