@inproceedings{13a64f99d4e849c4983a9265650b56b2,
title = "Timed comparisons of semi-Markov processes",
abstract = "Semi-Markov processes are Markovian processes in which the firing time of 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.",
keywords = "automata for system analysis and programme verification, probabilistic automata, real-time systems, semi-Markov processes",
author = "Pedersen, {Mathias R.} and Nathana{\"e}l Fijalkow and Giorgio Bacci and Larsen, {Kim G.} and Radu Mardare",
year = "2018",
month = mar,
day = "8",
doi = "10.1007/978-3-319-77313-1_21",
language = "English",
isbn = "9783319773124",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "271--283",
editor = "Klein, {Shmuel Tomi} and Carlos Mart{\'i}n-Vide and Dana Shapira",
booktitle = "Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings",
note = "12th International Conference on Language and Automata Theory and Applications, LATA 2018 ; Conference date: 09-04-2018 Through 11-04-2018",
}