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