Degree Type

Dissertation

Date of Award

2015

Degree Name

Doctor of Philosophy

Department

Computer Science

First Advisor

Andrew S. Miner

Abstract

In computer science, model checking refers to a computation process that, given a formal structure, checks whether the structure satisfies a logic formula which encodes certain properties. If the structure is a discrete state system and the interested properties depend only on which states to be reached, not on the time or probability to reach them, traditional temporal logics such as linear temporal logic (LTL) and computation tree logic (CTL) are powerful mathematical formalisms that can express properties such as ''no collision shall occur in a traffic light control system'', or ''eventually, a service is completed''. To express performance-dependability related properties over discrete state stochastic systems, these logics have evolved into quantitative model checking logics such as probabilistic linear temporal logic (PLTL), probabilistic computation tree logic (PCTL), and computation tree stochastic logic (CSL), etc., and can express properties such as ``with probability at least 0.98, the system will not reach a deadlock state before time 100''. While these logics and their model checking algorithms are powerful, they are inadequate in expressing complex performance measures, either because they are limited to producing only true/false responses (although in practice, a real valued response can sometimes be obtained for the outer-most path quantifier), or the computational complexity is too expensive to be practical.

To address these limitations, for this PhD work, we propose a novel mechanism with the following research aims: 1) Define general specification formalisms to express performance queries in real values while retaining the ability to express temporal properties. 2) Develop efficient mathematical algorithms for the proposed formalisms. 3)Implement the approach in tools and experiment on large-scaled Markov models for the analysis of example queries.

Copyright Owner

Yaping Jing

Language

en

File Format

application/pdf

File Size

131 pages

Share

COinS