Timed comparisons of semi-Markov processes

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

doi:10.1007/978-3-319-77313-1_21

Timed comparisons of semi-Markov processes

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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings
Editors	Shmuel Tomi Klein, Carlos Martín-Vide, Dana Shapira
Place of Publication	Cham
Publisher	Springer-Verlag
Pages	271-283
Number of pages	13
ISBN (Print)	9783319773124
DOIs	https://doi.org/10.1007/978-3-319-77313-1_21
Publication status	Published - 8 Mar 2018
Event	12th International Conference on Language and Automata Theory and Applications, LATA 2018 - Ramat Gan, Israel Duration: 9 Apr 2018 → 11 Apr 2018

Publication series

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

Conference

Conference	12th International Conference on Language and Automata Theory and Applications, LATA 2018
Country/Territory	Israel
City	Ramat Gan
Period	9/04/18 → 11/04/18

Funding

This work was supported by the Alan Turing Institute under the EPSRC grant EP/N510129/1, the Danish FTP project ASAP, the ERC Advanced Grant LASSO, and the Sino-Danish Basic Research Center IDEA4CPS.

Keywords

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

Access to Document

10.1007/978-3-319-77313-1_21

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

Pedersen, Mathias R. ; Fijalkow, Nathanaël ; Bacci, Giorgio et al. / Timed comparisons of semi-Markov processes. Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings. editor / Shmuel Tomi Klein ; Carlos Martín-Vide ; Dana Shapira. Cham : Springer-Verlag, 2018. pp. 271-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

}

Pedersen, MR, Fijalkow, N, Bacci, G, Larsen, KG & Mardare, R 2018, Timed comparisons of semi-Markov processes. in ST Klein, C Martín-Vide & D Shapira (eds), Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10792 LNCS, Springer-Verlag, Cham, pp. 271-283, 12th International Conference on Language and Automata Theory and Applications, LATA 2018, Ramat Gan, Israel, 9/04/18. https://doi.org/10.1007/978-3-319-77313-1_21

Timed comparisons of semi-Markov processes. / Pedersen, Mathias R.; Fijalkow, Nathanaël; Bacci, Giorgio et al.
Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings. ed. / Shmuel Tomi Klein; Carlos Martín-Vide; Dana Shapira. Cham: Springer-Verlag, 2018. p. 271-283 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10792 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

T1 - Timed comparisons of semi-Markov processes

AU - Pedersen, Mathias R.

AU - Fijalkow, Nathanaël

AU - Bacci, Giorgio

AU - Larsen, Kim G.

AU - Mardare, Radu

PY - 2018/3/8

Y1 - 2018/3/8

N2 - 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.

AB - 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.

KW - automata for system analysis and programme verification

KW - probabilistic automata

KW - real-time systems

KW - semi-Markov processes

UR - http://www.scopus.com/inward/record.url?scp=85045308889&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-77313-1_21

DO - 10.1007/978-3-319-77313-1_21

M3 - Conference contribution book

AN - SCOPUS:85045308889

SN - 9783319773124

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 271

EP - 283

BT - Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings

A2 - Klein, Shmuel Tomi

A2 - Martín-Vide, Carlos

A2 - Shapira, Dana

PB - Springer-Verlag

CY - Cham

T2 - 12th International Conference on Language and Automata Theory and Applications, LATA 2018

Y2 - 9 April 2018 through 11 April 2018

ER -

Pedersen MR, Fijalkow N, Bacci G, Larsen KG, Mardare R. Timed comparisons of semi-Markov processes. In Klein ST, Martín-Vide C, Shapira D, editors, Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings. Cham: Springer-Verlag. 2018. p. 271-283. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-77313-1_21

Timed comparisons of semi-Markov processes

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this