Author name cluster

David N. Jansen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

I&C Journal 2016 Journal Article

A space-efficient simulation algorithm on probabilistic automata

Lijun Zhang
David N. Jansen

In the context of probabilistic automata, time-efficient algorithms for simulation have been proposed lately. The space complexity thereof is quadratic in the size of the transition relation, thus space requirements often become the practical bottleneck. In this paper, we propose a space-efficient algorithm for computing simulation based on partition refinement. Experimental evidence is given showing that not only the space efficiency is improved drastically: The experiments often require orders of magnitude less time. In practice, they are even faster than the (asymptotically) optimal algorithm by Crafa and Ranzato (2012).

Details DOI

TCS Journal 2016 Journal Article

Multiphase until formulas over Markov reward models: An algebraic approach

Ming Xu
Lijun Zhang
David N. Jansen
Huibiao Zhu
Zongyuan Yang

We consider the probabilistic model checking problem of continuous-time Markov chains with rewards. We first extend multiphase until formulas in continuous stochastic logic (CSL) with reward constraints. Then we present an effective integral-style algorithm to compute the probability under the assumption of harmony, and give upper and lower bounds of the probability without this assumption. Furthermore, the resulting probability value (or its upper and lower bounds) is shown to be a real number of a well-formed structure, with which we can successfully (or partially) decide whether the constraints in the CSL formula are satisfied. Our method is entirely based on algebraic manipulations and number theory. Finally, to show the practical usefulness, we apply the results to evaluate the performance of a small multi-processor system.

Details DOI