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

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

1 Citationer (Scopus)

159 Downloads (Pure)

Abstrakt

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.

Originalsprog	Engelsk
Titel	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
Redaktører	Carlos Martin-Vide, Shmuel Tomi Klein, Dana Shapira
Antal sider	13
Forlag	Springer Publishing Company
Publikationsdato	2018
Sider	271-283
ISBN (Trykt)	978-3-319-77312-4
ISBN (Elektronisk)	978-3-319-77313-1
DOI	https://doi.org/10.1007/978-3-319-77313-1_21
Status	Udgivet - 2018
Begivenhed	International Conference on Language and Automata Theory and Applications - Ramat Gan, Israel Varighed: 9 apr. 2018 → 11 apr. 2018

Konference

Konference	International Conference on Language and Automata Theory and Applications
Land/Område	Israel
By	Ramat Gan
Periode	09/04/2018 → 11/04/2018

Navn	Lecture Notes in Computer Science
Nummer	10792
ISSN	0302-9743

Adgang til dokumentet

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

Timed Comparisons of Semi-Markov ProcessesAccepteret manuskript, 470 KB

Andre filer og links

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

Approximate Reasoning for Stochastic Markovian Systems
Mardare, R. & Larsen, K. G.
01/11/2015 → 31/10/2019
Projekter: Projekt › Forskning
IDEA4CPS: Foundations for Cyber-Physical Sytems
Larsen, K. G., Skou, A., Nielsen, B., Bulychev, P., Ravn, A. P. & Poulsen, D. B.
01/04/2011 → 30/04/2015
Projekter: Projekt › Forskning

Citationsformater

Pedersen, M. R., Fijalkow, N., Bacci, G., Larsen, K. G., & Mardare, R. I. (2018). Timed Comparisons of Semi-Markov Processes. I C. Martin-Vide, S. T. Klein, & D. Shapira (red.), 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 (s. 271-283). Springer Publishing Company. Lecture Notes in Computer Science Nr. 10792 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. red. / Carlos Martin-Vide ; Shmuel Tomi Klein ; Dana Shapira. Springer Publishing Company, 2018. s. 271-283 (Lecture Notes in Computer Science; Nr. 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. i C Martin-Vide, ST Klein & D Shapira (red), 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, nr. 10792, s. 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. red. / Carlos Martin-Vide; Shmuel Tomi Klein; Dana Shapira. Springer Publishing Company, 2018. s. 271-283 (Lecture Notes in Computer Science; Nr. 10792).

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › 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. I Martin-Vide C, Klein ST, Shapira D, red., 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. s. 271-283. (Lecture Notes in Computer Science; Nr. 10792). doi: 10.1007/978-3-319-77313-1_21

Timed Comparisons of Semi-Markov Processes

Abstrakt

Konference

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Projekter

Approximate Reasoning for Stochastic Markovian Systems

IDEA4CPS: Foundations for Cyber-Physical Sytems

Citationsformater