Advances in probabilistic model checking with PRISM: variable reordering,quantiles and weak deterministic Büchi automata

International Journal on Software Tools for Technology Transfer - The popular model checker PRISM has been successfully used for the modeling and analysis of complex probabilistic systems. As one...     

On the combination of logical and probabilistic models for?information analysis

Formal logical tools are able to provide some amount of reasoning support for information analysis, but are unable to represent uncertainty. Bayesian network tools represent probabilistic and causal information, but in the worst case scale as poorly as some formal logical systems and require specialized expertise to use effectively. We describe a framework for systems that incorporate the advantages of both Bayesian and logical systems. We define a formalism for the conversion of automatically generated natural deduction proof trees into Bayesian networks. We then demonstrate that the merging of such networks with domain-specific causal models forms a consistent Bayesian network with correct values for the formulas derived in the proof. In particular, we show that hard evidential updates in which the premises of a proof are found to be true force the conclusions of the proof to be true with probability one, regardless of any dependencies and prior probability values assumed for the causal model. We provide several examples that demonstrate the generality of the natural deduction system by using inference schemes not supportable directly in Horn clause logic. We compare our approach to other ones, including some that use non-standard logics.     

On the universal zero attractor of the Tribonacci-related polynomials

In this paper we solve a conjecture on the zeros of R-Bonacci polynomials in the case when r=3 (Tribonacci polynomials) and determine the zero attractor of the Tribonacci polynomials. Universality of the zero attractor is also established.      

Mining probabilistic automata: a statistical view of sequential pattern mining

During the past decade, sequential pattern mining has been the core of numerous research efforts. It is now possible to efficiently extract knowledge of users’ behavior from a huge set of sequences collected over time. This has applications in various domains such as purchases in supermarkets, Web site visits, etc. However, sequence mining algorithms do little to control the risks of extracting false discoveries or overlooking true knowledge. In this paper, the theoretical conditions to achieve a relevant sequence mining process are examined. Then, the article offers a statistical view of sequence mining which has the following advantages: First, it uses a compact and generalized representation of the original sequences in the form of a probabilistic automaton. Second, it integrates statistical constraints to guarantee the extraction of significant patterns. Finally, it provides an interesting solution in a privacy preserving context in order to respect individuals’ information. An application in car flow modeling is presented, showing the ability of our algorithm (acsm) to discover frequent routes without any private information. Comparisons with a classical sequence mining algorithm (spam) are made, showing the effectiveness of our approach.     

A logical encoding of the π-calculus: model checking mobile processes using tabled resolution

We present MMC, a model checker for mobile systems specified in the style of the -calculus. MMCs development builds on that of XMC, a model checker for an expressive extension of Milners value-passing calculus implemented using the XSB tabled logic-programming engine. MMC addresses the salient issues that arise in the -calculus, including scope extrusion and intrusion and dynamic generation of new names to avoid name capture. We show that logic programming provides an efficient implementation platform for model checking -calculus specifications and can be used to obtain an exact encoding of the -calculuss transitional semantics. Moreover, MMC is easily extended to handle process expressions in the spi-calculus of Abadi and Gordon. Our experimental data show that MMC outperforms other known tools for model checking the -calculus.     

Combining search space partition and abstraction for LTL model checking

The state space explosion problem is still the key obstacle for applying model checking to systems of industrial size. Abstraction-based methods have been particularly successful in this regard. This paper presents an approach based on refinement of search space partition and abstraction which combines these two techniques for reducing the complexity of model checking. The refinement depends on the representation of each portion of search space. Especially, search space can be refined stepwise to get a better reduction. As reported in the case study, the integration of search space partition and abstraction improves the efficiency of verification with respect to the requirement of memory and obtains significant advantage over the use of each of them in isolation.     

On the application of the minimum polynomial extrapolation method to incompressible flows with heat transfer

In this paper, the Minimum Polynomial Extrapolation method (MPE) is used to accelerate the convergence of the Characteristic–Based–Split (CBS) scheme for the numerical solution of steady state incompressible flows with heat transfer. The CBS scheme is a fractional step method for the solution of the Navier–Stokes equations while the MPE method is a vector extrapolation method which transforms the original sequence into another sequence converging to the same limit faster then the original one without the explicit knowledge of the sequence generator. The developed algorithm is tested on a two-dimensional benchmark problem (buoyancy–driven convection problem) where the Navier–Stokes equations are coupled with the temperature equation. The obtained results show the feature of the extrapolation procedure to the CBS scheme and the reduction of the computational time of the simulation.     

Practical CTL* model checking: Should SPIN be extended?

We describe an efficient CTL^* model checking algorithm based on alternating automata and games. A CTL^* formula, expressing a correctness property, is first translated to a hesitant alternating automaton and then composed with a Kripke structure representing the model to be checked, after which this resulting automaton is then checked for nonemptiness. We introduce the nonemptiness game that checks the nonemptiness of a hesitant alternating automaton (HAA). In the same way that alternating automata generalise nondeterministic automata, we show that this game for checking the nonemptiness of HAA, generalises the nested depth-first algorithm used to check the nonemptiness of nondeterministic Büchi automata (used in Spin).     

On Hierarchical Diameter-Clustering and the Supplier Problem

Given a data set in a metric space, we study the problem of hierarchical clustering to minimize the maximum cluster diameter, and the hierarchical k-supplier problem with customers arriving online. We prove that two previously known algorithms for hierarchical clustering, one (offline) due to Dasgupta and Long and the other (online) due to Charikar, Chekuri, Feder and Motwani, output essentially the same result when points are considered in the same order. We show that the analyses of both algorithms are tight and exhibit a new lower bound for hierarchical clustering. Finally we present the first constant factor approximation algorithm for the online hierarchical k-supplier problem.     

On Independent Vertex Sets in Subclasses of Apple-Free Graphs

In a finite undirected graph, an apple consists of a chordless cycle of length at least 4, and an additional vertex which is not in the cycle and sees exactly one of the cycle vertices. A graph is apple-free if it contains no induced subgraph isomorphic to an apple. Apple-free graphs are a common generalization of chordal graphs, claw-free graphs and cographs and occur in various papers. The Maximum Weight Independent Set (MWS) problem is efficiently solvable on chordal graphs, on cographs as well as on claw-free graphs. In this paper, we obtain partial results on some subclasses of apple-free graphs where our results show that the MWS problem is solvable in polynomial time. The main tool is a combination of clique separators with modular decomposition. Our algorithms are robust in the sense that there is no need to recognize whether the input graph is in the given graph class; the algorithm either solves the MWS problem correctly or detects that the input graph is not in the given class.     

Psychological model of particle swarm optimization based multiple emotions

This paper proposes a novel approach to swarm particle optimization based on emotional behavior to solve real optimization problems. In the trend of PSO manipulating self-adaptive control to regulate potential parameters, the proposed algorithm involves both a semi-adaptive inertia weight and an emotional factor at the level of the velocity rule. The semi-inertia weight highlights a specific comportment. Thus, due to the few changes occurred in its adaptive “life”, it continues to evolve with a significantly smaller constant for the benefit of a finer exploitation. The emotion factor presents an important feature of convergence because it splits up the search space into potential regions that are finely explored by sub-swarm populations with the same emotions. The principle of particles with multiple emotions intended for the categorization of particles into specific emotional classes. The idea behind this principle is to divide to conquer, and due to presence of multiple emotional classes the multidimensional search space is widely explored at the search of the best position. Emotional PSO is evaluated on the test suit of 25 functions designed for the special session on real optimization of CEC 2005, and its performances are compared to the best algorithm the restart CMA-ES.     

On the Black-Box Complexity of Sperner’s Lemma

We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an lower bound for its probabilistic, and an lower bound for its quantum query complexity, showing that all these measures are polynomially related. Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559 and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry.     

Vesicles and Amoebae: On Globally Constrained Shape Deformation

Modeling the deformation of shapes under constraints on both perimeter and area is a challenging task due to the highly nontrivial interaction between the need for flexible local rules for manipulating the boundary and the global constraints. We propose several methods to address this problem and generate “random walks” in the space of shapes obeying quite general possibly time varying constraints on their perimeter and area. Design of perimeter and area preserving deformations are an interesting and useful special case of this problem. The resulting deformation models are employed in annealing processes that evolve original shapes toward shapes that are optimal in terms of boundary bending-energy or other functionals. Furthermore, such models may find applications in the analysis of sequences of real images of deforming objects obeying global constraints as building blocks for registration and tracking algorithms.     

Multi-body model of a bobsleigh: comparison with experimental data

Bobsleigh is a winter sport in which teams make timed runs down narrow, twisting, banked, iced tracks in gravity-powered sleds. To win the race, it is of great importance to have a sled that is optimized from both the sliding and the aerodynamic point of view. However, also typical vehicle parameters, such as the weight distribution and the inclination of the steering axis, play an important role. In fact, being the friction coefficient between skates and ice very small (approx. 0.04), a change in the weight acting on the front skates may significantly modify the steering feedback of the driver thus highlighting his/her driving ability. Better trajectories imply less correction on the steering axis, and thus better performances. The inclination of the steering axis, instead, generates a torque similar to the self-aligning torque produced by road vehicle tires thus stabilizing the front skates and requiring less control actions to the sled driver.     

On the applicability of word sense discrimination on 201 years of modern english

As language evolves over time, documents stored in long- term archives become inaccessible to users. Automatically, detecting and handling language evolution will become a necessity to meet user’s information needs. In this paper, we investigate the performance of modern tools and algorithms applied on modern English to find word senses that will later serve as a basis for finding evolution. We apply the curvature clustering algorithm on all nouns and noun phrases extracted from The Times Archive (1785–1985). We use natural language processors for part-of-speech tagging and lemmatization and report on the performance of these processors over the entire period. We evaluate our clusters using WordNet to verify whether they correspond to valid word senses. Because The Times Archive contains OCR errors, we investigate the effects of such errors on word sense discrimination results. Finally, we present a novel approach to correct OCR errors present in the archive and show that the coverage of the curvature clustering algorithm improves. We increase the number of clusters by 24 %. To verify our results, we use the New York Times corpus (1987–2007), a recent collection that is considered error free, as a ground truth for our experiments. We find that after correcting OCR errors in The Times Archive, the performance of word sense discrimination applied on The Times Archive is comparable to the ground truth.     

Generating phenotypical erroneous human behavior to evaluate human–automation interaction using model checking

Breakdowns in complex systems often occur as a result of system elements interacting in unanticipated ways. In systems with human operators, human–automation interaction associated with both normative and erroneous human behavior can contribute to such failures. Model-driven design and analysis techniques provide engineers with formal methods tools and techniques capable of evaluating how human behavior can contribute to system failures. This paper presents a novel method for automatically generating task analytic models encompassing both normative and erroneous human behavior from normative task models. The generated erroneous behavior is capable of replicating Hollnagel's zero-order phenotypes of erroneous action for omissions, jumps, repetitions, and intrusions. Multiple phenotypical acts can occur in sequence, thus allowing for the generation of higher order phenotypes. The task behavior model pattern capable of generating erroneous behavior can be integrated into a formal system model so that system safety properties can be formally verified with a model checker. This allows analysts to prove that a human–automation interactive system (as represented by the model) will or will not satisfy safety properties with both normative and generated erroneous human behavior. We present benchmarks related to the size of the statespace and verification time of models to show how the erroneous human behavior generation process scales. We demonstrate the method with a case study: the operation of a radiation therapy machine. A potential problem resulting from a generated erroneous human action is discovered. A design intervention is presented which prevents this problem from occurring. We discuss how our method could be used to evaluate larger applications and recommend future paths of development.     

Theoretical vibration analysis of soft mounted electrical machines regarding rotor eccentricity based on a multibody model

The paper presents a simplified multibody model of a soft mounted electrical machine for theoretical vibration analysis, considering different kinds of rotor eccentricity. The most important dynamic eccentricities in electrical machines—eccentricity of rotor mass, magnetic eccentricity, and bent rotor deflection—are analyzed. The aim of the paper is not to replace a detailed three-dimensional finite-element calculation by a simplified plane multibody model, but to show the mathematical correlation between rotor dynamics, electromagnetic influence, oil film characteristics of the sleeve bearings, the influence of a soft foundation, and excitations by different kinds of rotor eccentricity, based on a simplified analytical model. Beside the absolute orbits of the rotor, stator, shaft journals, and bearing housings, also the relative orbits between rotor and stator and between shaft journals and bearing housings are mathematically described. In addition to these theoretical considerations, a numerical example for a soft mounted 2-pole induction motor is also shown. Finally, the paper shows the possibility of optimizing the system—electrical machine and foundation—regarding vibrations, caused by rotor eccentricities.     

Sleep–wake up scheduling with probabilistic coverage model in sensor networks1

Energy optimisation is one of the important issues in the research of wireless sensor networks (WSNs). In the application of monitoring, a large number of sensors are scattered uniformly to cover a collection of points of interest (PoIs) distributed randomly in the monitored area. Since the energy of battery-powered sensor is limited in WSNs, sensors are scheduled to wake up in a large-scale sensor network application. In this paper, we consider how to reduce the energy consumption and prolong the lifetime of WSNs through wake-up scheduling with probabilistic sensing model in the large-scale application of monitoring. To extend the lifetime of sensor network, we need to balance the energy consumption of sensors so that there will not be too much redundant energy in some sensors before the WSN terminates. The detection probability and false alarm probability are taken into consideration to achieve a better performance and reveal the real sensing process which is characterised in the probabilistic sensing model. Data fusion is also introduced to utilise information of sensors so that a PoI in the monitored area may be covered by multiple sensors collaboratively, which will decrease the number of sensors that cover the monitored region. Based on the probabilistic model and data fusion, minimum weight probabilistic coverage problem is formulated in this paper. We also propose a greedy method and modified genetic algorithm based on the greedy method to address the problem. Simulation experiments are conducted to demonstrate the advantages of our proposed algorithms over existing work.     

On the Use of Compact Streamfunction-Velocity Formulation of Steady Navier-Stokes Equations on Geometries beyond Rectangular

In this paper, a new methodology has been proposed to solve two-dimensional (2D) Navier-Stokes (N-S) equations representing incompressible viscous fluid flows on irregular geometries. It is based on second order compact finite difference discretization of the fourth order streamfunction equation on computational plane. The important advantage of this formulation is not only to overcome the difficulties existing in the velocity-pressure and streamfunction-vorticity formulations, but also for being applicable to complex geometries beyond rectangular. We first apply the proposed scheme to a problem having analytical solution and then to the well-studied benchmark problem (problem of lid-driven cavity flow) in viscous fluid flow. Finally, we demonstrate the robustness of our proposed scheme on flow in a complex domain (e.g. constricted channel and dilated channel). It is seen to efficiently capture steady state solutions of the N-S equations with Dirichlet as well as Neumann boundary conditions. In addition to this, it captures viscous flows involving free and wall bounded shear layers which invariably contain spatial scale variations. Estimates of the error incurred show that the results are very accurate on a coarser grid. The results obtained using this scheme are in excellent agreement with analytical and numerical results whenever available and they clearly demonstrate the superior scale resolution of the proposed scheme.