Timed Comparisons of Semi-Markov Processes

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

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

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 proceeding › Article in proceeding › Research › peer-review

1 Citation (Scopus)

185 Downloads (Pure)

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 : 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings
Editors	Carlos Martin-Vide, Shmuel Tomi Klein, Dana Shapira
Number of pages	13
Publisher	Springer Publishing Company
Publication date	2018
Pages	271-283
ISBN (Print)	978-3-319-77312-4
ISBN (Electronic)	978-3-319-77313-1
DOIs	https://doi.org/10.1007/978-3-319-77313-1_21
Publication status	Published - 2018
Event	International Conference on Language and Automata Theory and Applications - Ramat Gan, Israel Duration: 9 Apr 2018 → 11 Apr 2018

Conference

Conference	International Conference on Language and Automata Theory and Applications
Country/Territory	Israel
City	Ramat Gan
Period	09/04/2018 → 11/04/2018

Series	Lecture Notes in Computer Science
Number	10792
ISSN	0302-9743

Keywords

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

Access to Document

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

Timed Comparisons of Semi-Markov ProcessesAccepted author manuscript, 470 KB

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

Pedersen, M. R., Fijalkow, N., Bacci, G., Larsen, K. G., & Mardare, R. I. (2018). Timed Comparisons of Semi-Markov Processes. In C. Martin-Vide, S. T. Klein, & D. Shapira (Eds.), Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings: 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings (pp. 271-283). Springer Publishing Company. https://doi.org/10.1007/978-3-319-77313-1_21

Pedersen, Mathias Ruggaard ; 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: 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings. editor / Carlos Martin-Vide ; Shmuel Tomi Klein ; Dana Shapira. Springer Publishing Company, 2018. pp. 271-283 (Lecture Notes in Computer Science; No. 10792).

@inproceedings{ebdc794f80c444cebdb43b416c4f99d0,

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-Markovprocesses.",

keywords = "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",

author = "Pedersen, {Mathias Ruggaard} and Nathana{\"e}l Fijalkow and Giorgio Bacci and Larsen, {Kim Guldstrand} and Mardare, {Radu Iulian}",

year = "2018",

doi = "10.1007/978-3-319-77313-1_21",

language = "English",

isbn = "978-3-319-77312-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer Publishing Company",

number = "10792",

pages = "271--283",

editor = "Carlos Martin-Vide and Klein, {Shmuel Tomi} and Dana Shapira",

booktitle = "Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings",

address = "United States",

note = "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, RI 2018, Timed Comparisons of Semi-Markov Processes. in C Martin-Vide, ST Klein & D Shapira (eds), Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings: 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings. Springer Publishing Company, Lecture Notes in Computer Science, no. 10792, pp. 271-283, International Conference on Language and Automata Theory and Applications, Ramat Gan, Israel, 09/04/2018. https://doi.org/10.1007/978-3-319-77313-1_21

Timed Comparisons of Semi-Markov Processes. / Pedersen, Mathias Ruggaard; Fijalkow, Nathanaël; Bacci, Giorgio et al.
Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings: 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings. ed. / Carlos Martin-Vide; Shmuel Tomi Klein; Dana Shapira. Springer Publishing Company, 2018. p. 271-283 (Lecture Notes in Computer Science; No. 10792).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - Timed Comparisons of Semi-Markov Processes

AU - Pedersen, Mathias Ruggaard

AU - Fijalkow, Nathanaël

AU - Bacci, Giorgio

AU - Larsen, Kim Guldstrand

AU - Mardare, Radu Iulian

PY - 2018

Y1 - 2018

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

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

KW - semi-markov process

KW - real-time

KW - faster-than preorder

KW - probabilistic automata

KW - Probabilistic automata

KW - Semi-Markov processes

KW - Real-time systems

KW - Automata for system analysis and programme verification

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 - Article in proceeding

SN - 978-3-319-77312-4

T3 - Lecture Notes in Computer Science

SP - 271

EP - 283

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

A2 - Martin-Vide, Carlos

A2 - Klein, Shmuel Tomi

A2 - Shapira, Dana

PB - Springer Publishing Company

T2 - International Conference on Language and Automata Theory and Applications

Y2 - 9 April 2018 through 11 April 2018

ER -

Pedersen MR, Fijalkow N, Bacci G , Larsen KG, Mardare RI. Timed Comparisons of Semi-Markov Processes. In Martin-Vide C, Klein ST, Shapira D, editors, Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings: 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings. Springer Publishing Company. 2018. p. 271-283. (Lecture Notes in Computer Science; No. 10792). doi: 10.1007/978-3-319-77313-1_21

Timed Comparisons of Semi-Markov Processes

Abstract

Conference

Keywords

Access to Document

AUB Link

Other files and links

Fingerprint

Approximate Reasoning for Stochastic Markovian Systems

IDEA4CPS: Foundations for Cyber-Physical Sytems

Cite this

Timed Comparisons of Semi-Markov Processes

Abstract

Conference

Keywords

Access to Document

AUB Link

Other files and links

Fingerprint

Projects

Approximate Reasoning for Stochastic Markovian Systems

IDEA4CPS: Foundations for Cyber-Physical Sytems

Cite this