Electronic Notes in Theoretical Computer Science · 2006 · 56 citations · 13 references
ComputingComputer ScienceFormal MethodsMarkov Decision ProcessesTheory Of ComputationDeductive VerificationFinite State Machine ModelingMarkov ProcessesModel CheckingTemporal LogicBranching TimeComputation Tree LogicComputational Tree LogicPartial-order ReductionProbabilistic ComputationProbabilistic LogicProbabilistic Model CheckingState Space Explosion
In the past, partial order reduction has been used successfully to combat the state explosion problem in the context of model checking for non-probabilistic systems. For both linear time and branching time specifications, methods have been developed to apply partial order reduction in the context of model checking. Only recently, results were published that give criteria on applying partial order reduction for verifying quantitative linear time properties for probabilistic systems. This paper presents partial order reduction criteria for Markov decision processes and branching time properties, such as formulas of probabilistic computation tree logic. Moreover, we provide a comparison of the results established so far about reduction conditions for Markov decision processes.
13
A logic for reasoning about time and reliability
Hans Hansson, Bengt Jönsson · Formal Aspects of Computing · 1994 · 1.4K citations · Full text
A stubborn attack on state explosion
Antti Valmari · Formal Methods in System Design · 1992 · 575 citations