Timed Comparisons of Semi-Markov Processes

Mathias Ruggaard Pedersen, Nathanaël Fijalkow, Giorgio Bacci, Kim Guldstrand Larsen, Radu Iulian Mardare

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

1 Citation (Scopus)
144 Downloads (Pure)


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
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings : 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings
EditorsCarlos Martin-Vide, Shmuel Tomi Klein, Dana Shapira
Number of pages13
PublisherSpringer Publishing Company
Publication date2018
ISBN (Print)978-3-319-77312-4
ISBN (Electronic)978-3-319-77313-1
Publication statusPublished - 2018
EventInternational Conference on Language and Automata Theory and Applications - Ramat Gan, Israel
Duration: 9 Apr 201811 Apr 2018


ConferenceInternational Conference on Language and Automata Theory and Applications
CityRamat Gan
SeriesLecture Notes in Computer Science


  • semi-markov process
  • real-time
  • faster-than preorder
  • probabilistic automata
  • Probabilistic automata
  • Semi-Markov processes
  • Real-time systems
  • Automata for system analysis and programme verification


Dive into the research topics of 'Timed Comparisons of Semi-Markov Processes'. Together they form a unique fingerprint.

Cite this