The Experts below are selected from a list of 18888 Experts worldwide ranked by ideXlab platform

Cong Tian - One of the best experts on this subject based on the ideXlab platform.

  • symbolic Model Checking for propositional projection temporal logic
    Theoretical Aspects of Software Engineering, 2012
    Co-Authors: Tao Pang, Zhenhua Duan, Cong Tian
    Abstract:

    This paper presents a symbolic Model Checking Algorithm for Propositional Projection Temporal Logic (PPTL). Within this method, the Model of a system is specified by aKripke structure M, and the desired property is specified in aPPTL formula P. First, Mis symbolically represented with Boolean functions while !P is transformed into its normal form. Then the set of states in Mthat satisfies !P, namely Sat(!P), is computed recursively with respect to the transition relations. Thus, whether the system satisfies the property can be equivalently checked by determining the emptiness of Sat(!P). All the operations above can be implemented by a graph Algorithm operated on ROBDDs.

  • an improved decision procedure for propositional projection temporal logic
    International Conference on Formal Engineering Methods, 2010
    Co-Authors: Zhenhua Duan, Cong Tian
    Abstract:

    A new decision procedure for Propositional Projection Temporal Logic (PPTL) is proposed which is an improvement to the decision procedure given in [4]. The main contribution of the paper is as follows: (1) the relationship between paths in the NFG of a formula R and its Models is established and proved; (2) a new Labeled NFG (LNFG) with a set of labels (propositions) is defined; (3) given a formula R, an LNFG of R can be generated by the new decision Algorithm, and all Models of R can be found; (4) based on the new decision procedure, an improved Model Checking Algorithm is presented and implemented.

  • Model Checking propositional projection temporal logic based on spin
    Formal Methods, 2007
    Co-Authors: Cong Tian, Zhenhua Duan
    Abstract:

    This paper investigates a Model Checking Algorithm for Propositional Projection Temporal Logic (PPTL) with finite Models. To this end, a PPTL formula is transformed to a Normal Form Graph (NFG), and then a Nondeterministic Finite Automaton (NFA). The NFA precisely characterizes the finite Models satisfying the corresponding formula and can be equivalently represented as a Deterministic Finite Automaton (DFA). When the system to be verified can be Modeled as a DFA As, and the property of the system can be specified by a PPTL formula P, then ¬P can be transformed to a DFA Ap. Thus, whether the system satisfies the property or not can be checked by computing the product automaton of As and Ap, and then Checking whether or not the product automaton accepts the empty word. Further, this method can be implemented by means of the verification system SPIN.

Zhenhua Duan - One of the best experts on this subject based on the ideXlab platform.

  • symbolic Model Checking for propositional projection temporal logic
    Theoretical Aspects of Software Engineering, 2012
    Co-Authors: Tao Pang, Zhenhua Duan, Cong Tian
    Abstract:

    This paper presents a symbolic Model Checking Algorithm for Propositional Projection Temporal Logic (PPTL). Within this method, the Model of a system is specified by aKripke structure M, and the desired property is specified in aPPTL formula P. First, Mis symbolically represented with Boolean functions while !P is transformed into its normal form. Then the set of states in Mthat satisfies !P, namely Sat(!P), is computed recursively with respect to the transition relations. Thus, whether the system satisfies the property can be equivalently checked by determining the emptiness of Sat(!P). All the operations above can be implemented by a graph Algorithm operated on ROBDDs.

  • an improved decision procedure for propositional projection temporal logic
    International Conference on Formal Engineering Methods, 2010
    Co-Authors: Zhenhua Duan, Cong Tian
    Abstract:

    A new decision procedure for Propositional Projection Temporal Logic (PPTL) is proposed which is an improvement to the decision procedure given in [4]. The main contribution of the paper is as follows: (1) the relationship between paths in the NFG of a formula R and its Models is established and proved; (2) a new Labeled NFG (LNFG) with a set of labels (propositions) is defined; (3) given a formula R, an LNFG of R can be generated by the new decision Algorithm, and all Models of R can be found; (4) based on the new decision procedure, an improved Model Checking Algorithm is presented and implemented.

  • Model Checking propositional projection temporal logic based on spin
    Formal Methods, 2007
    Co-Authors: Cong Tian, Zhenhua Duan
    Abstract:

    This paper investigates a Model Checking Algorithm for Propositional Projection Temporal Logic (PPTL) with finite Models. To this end, a PPTL formula is transformed to a Normal Form Graph (NFG), and then a Nondeterministic Finite Automaton (NFA). The NFA precisely characterizes the finite Models satisfying the corresponding formula and can be equivalently represented as a Deterministic Finite Automaton (DFA). When the system to be verified can be Modeled as a DFA As, and the property of the system can be specified by a PPTL formula P, then ¬P can be transformed to a DFA Ap. Thus, whether the system satisfies the property or not can be checked by computing the product automaton of As and Ap, and then Checking whether or not the product automaton accepts the empty word. Further, this method can be implemented by means of the verification system SPIN.

Holger Hermanns - One of the best experts on this subject based on the ideXlab platform.

  • towards Model Checking stochastic process algebra
    Integrated Formal Methods, 2000
    Co-Authors: Holger Hermanns, Joostpieter Katoen, J Meyerkayser, Markus Siegle
    Abstract:

    Stochastic process algebras have been proven useful because they allow behaviour-oriented performance and reliability Modelling. As opposed to traditional performance Modelling techniques, the behaviour-oriented style supports composition and abstraction in a natural way. However, analysis of stochastic process algebra Models is state-oriented, because standard numerical analysis is typically based on the calculation of (transient and steady) state probabilities. This shift of paradigms hampers the acceptance of the process algebraic approach by performance Modellers. In this paper, we develop an entirely behaviour-oriented analysis technique for stochastic process algebras. The key contribution is an action-based temporal logic to describe behaviours-of-interest, together with a Model Checking Algorithm to derive the probability with which a stochastic process algebra Model exhibits a given behaviour-of-interest.

  • approximate symbolic Model Checking of continuous time markov chains
    Lecture Notes in Computer Science, 1999
    Co-Authors: Christel Baier, Joostpieter Katoen, Holger Hermanns
    Abstract:

    This paper presents a symbolic Model Checking Algorithm for continuous-time Markov chains for an extension of the continuous stochastic logic CSL of Aziz et al [1]. The considered logic contains a time-bounded until-operator and a novel operator to express steady-state probabilities. We show that the Model Checking problem for this logic reduces to a system of linear equations (for unbounded until and the steady state-operator) and a Volterra integral equation system for time-bounded until. We propose a symbolic approximate method for solving the integrals using MTDDs (multi-terminal decision diagrams), a generalisation of MTBDDs. These new structures are suitable for numerical integration using quadrature formulas based on equally-spaced abscissas. like trapezoidal, Simpson and Romberg integration schemes.

Bernhard Steffen - One of the best experts on this subject based on the ideXlab platform.

  • Model Checking the full modal mu calculus for infinite sequential processes
    Theoretical Computer Science, 1999
    Co-Authors: Olaf Burkart, Bernhard Steffen
    Abstract:

    In this paper we develop a new exponential Algorithm for Model-Checking infinite sequential processes, including context-free processes, pushdown processes, and regular graphs, that decides the full modal mu-calculus. Whereas the actual Model Checking Algorithm results from considering conditional semantics together with backtracking caused by alternation, the corresponding correctness proof requires a stronger framework, which uses dynamic environments Modelled by finite-state automata.

  • a linear time Model Checking Algorithm for the alternation free modal mu calculus
    Computer Aided Verification, 1993
    Co-Authors: Rance Cleaveland, Bernhard Steffen
    Abstract:

    We develop a Model-Checking Algorithm for a logic that permits propositions to be defined with greatest and least fixed points of mutually recursive systems of equations. This logic is as expressive as the alternation-free fragment of the modal mu-calculus identified by Emerson and Lei, and it may therefore be used to encode a number of temporal logics and behavioral preorders. Our Algorithm determines whether a process satisfies a formula in time proportional to the product of the sizes of the process and the formula; this improves on the best known Algorithm for similar fixed-point logics.

Christel Baier - One of the best experts on this subject based on the ideXlab platform.

  • symbolic Model Checking for channel based component connectors
    Science of Computer Programming, 2009
    Co-Authors: Sascha Kluppelholz, Christel Baier
    Abstract:

    This paper introduces a temporal logic framework to reason about the coordination mechanisms and data flow of exogenous coordination Models. We take a CTL-like branching time logic, augmented with regular expressions that specify the observable I/O-operations, as a starting point. The paper provides the syntax and semantics of our logic and introduces the corresponding Model Checking Algorithm. The second part of the paper reports an implementation that relies on a symbolic representation of the coordination network and the connected components by means of binary decision diagrams. A couple of examples are given to illustrate the efficiency of the Model Checking techniques and their implementation.

  • symbolic Model Checking for channel based component connectors
    Electronic Notes in Theoretical Computer Science, 2007
    Co-Authors: Sascha Kluppelholz, Christel Baier
    Abstract:

    The paper reports on the foundations and experimental results with a Model checker for component connectors Modelled by networks of channels in the calculus Reo. The specification formalisms is a branching time logic that allows to reason about the coordination principles of and the data flow in the network. The underlying Model Checking Algorithm relies on variants of standard automata-based approaches and Model Checking for CTL-like logics. The implementation uses a symbolic representation of the network and the enabled I/O-operations by means of binary decision diagrams. It has been applied to a couple examples that illustrate the efficiency of our Model checker.

  • approximate symbolic Model Checking of continuous time markov chains
    Lecture Notes in Computer Science, 1999
    Co-Authors: Christel Baier, Joostpieter Katoen, Holger Hermanns
    Abstract:

    This paper presents a symbolic Model Checking Algorithm for continuous-time Markov chains for an extension of the continuous stochastic logic CSL of Aziz et al [1]. The considered logic contains a time-bounded until-operator and a novel operator to express steady-state probabilities. We show that the Model Checking problem for this logic reduces to a system of linear equations (for unbounded until and the steady state-operator) and a Volterra integral equation system for time-bounded until. We propose a symbolic approximate method for solving the integrals using MTDDs (multi-terminal decision diagrams), a generalisation of MTBDDs. These new structures are suitable for numerical integration using quadrature formulas based on equally-spaced abscissas. like trapezoidal, Simpson and Romberg integration schemes.

  • Model Checking for a probabilistic branching time logic with fairness
    Distributed Computing, 1998
    Co-Authors: Christel Baier, Marta Kwiatkowska
    Abstract:

    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 of [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.