Timed comparisons of semi-Markov processes

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

1 Citation (Scopus)

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.

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings
EditorsShmuel Tomi Klein, Carlos Martín-Vide, Dana Shapira
Place of PublicationCham
PublisherSpringer-Verlag
Pages271-283
Number of pages13
ISBN (Print)9783319773124
DOIs
Publication statusPublished - 8 Mar 2018
Event12th International Conference on Language and Automata Theory and Applications, LATA 2018 - Ramat Gan, Israel
Duration: 9 Apr 201811 Apr 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10792 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Language and Automata Theory and Applications, LATA 2018
CountryIsrael
CityRamat Gan
Period9/04/1811/04/18

Keywords

  • automata for system analysis and programme verification
  • probabilistic automata
  • real-time systems
  • semi-Markov processes

Fingerprint Dive into the research topics of 'Timed comparisons of semi-Markov processes'. Together they form a unique fingerprint.

  • Cite this

    Pedersen, M. R., Fijalkow, N., Bacci, G., Larsen, K. G., & Mardare, R. (2018). Timed comparisons of semi-Markov processes. In S. T. Klein, C. Martín-Vide, & D. Shapira (Eds.), Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings (pp. 271-283). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10792 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-319-77313-1_21