Timed comparisons of semi-Markov processes

DOI10.1007/978-3-319-77313-1_21MaRDI QIDQ1647713zbMATH OpenOpenAlexFDO

Authors Nathanaël Fijalkow, Giorgio Bacci, Radu Mardare, Mathias Ruggaard Pedersen, Kim G. Larsen

Publication date 26 June 2018

Full work available at URL https://arxiv.org/abs/1711.10216

zbMATH Keywords

probabilistic automataautomatareal-time systemsprogram verificationsemi-Markov processessystem analysis

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Markov renewal processes, semi-Markov processes (60K15) Specification and verification (program logics, model checking, etc.) (68Q60)

Abstract: Semi-Markov processes are Markovian processes in which the firing time of the transitions is modelled by probabilistic distributions over positive reals interpreted as the probability of firing a transition at a certain moment in time. In this paper we consider the trace-based semantics of semi-Markov processes, and investigate the question of how to compare two semi-Markov processes with respect to their time-dependent behaviour. To this end, we introduce the relation of being "faster than" between processes and study its algorithmic complexity. Through a connection to probabilistic automata we obtain hardness results showing in particular that this relation is undecidable. However, we present an additive approximation algorithm for a time-bounded variant of the faster-than problem over semi-Markov processes with slow residence-time functions, and a coNP algorithm for the exact faster-than problem over unambiguous semi-Markov processes.

Recommendations

• Semi-Markov processes in timed stochastic Petri nets
• A Hemimetric Extension of Simulation for Semi-Markov Decision Processes
• On the total variation distance of semi-Markov chains
• The theory of interactive generalized semi-Markov processes
• scientific article; zbMATH DE number 1884412

Cited in

(5)

• On the total variation distance of semi-Markov chains
• Comparison of level-crossing times for Markov and semi-Markov processes
• A Hemimetric Extension of Simulation for Semi-Markov Decision Processes
• Comparative branching-time semantics for Markov chains
• scientific article; zbMATH DE number 2087804 (Why is no real title available?)

This page was built for publication: Timed comparisons of semi-Markov processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1647713)