TY - GEN
T1 - Fixed-delay events in generalized semi-Markov processes revisited
AU - Brázdil, Tomáš
AU - Krčál, Jan
AU - Křetínský, Jan
AU - Řehák, Vojtěch
PY - 2011
Y1 - 2011
N2 - We study long run average behavior of generalized semi-Markov processes with both fixed-delay events as well as variable-delay events. We show that allowing two fixed-delay events and one variable-delay event may cause an unstable behavior of a GSMP. In particular, we show that a frequency of a given state may not be defined for almost all runs (or more generally, an invariant measure may not exist). We use this observation to disprove several results from literature. Next we study GSMP with at most one fixed-delay event combined with an arbitrary number of variable-delay events. We prove that such a GSMP always possesses an invariant measure which means that the frequencies of states are always well defined and we provide algorithms for approximation of these frequencies. Additionally, we show that the positive results remain valid even if we allow an arbitrary number of reasonably restricted fixed-delay events.
AB - We study long run average behavior of generalized semi-Markov processes with both fixed-delay events as well as variable-delay events. We show that allowing two fixed-delay events and one variable-delay event may cause an unstable behavior of a GSMP. In particular, we show that a frequency of a given state may not be defined for almost all runs (or more generally, an invariant measure may not exist). We use this observation to disprove several results from literature. Next we study GSMP with at most one fixed-delay event combined with an arbitrary number of variable-delay events. We prove that such a GSMP always possesses an invariant measure which means that the frequencies of states are always well defined and we provide algorithms for approximation of these frequencies. Additionally, we show that the positive results remain valid even if we allow an arbitrary number of reasonably restricted fixed-delay events.
UR - http://www.scopus.com/inward/record.url?scp=80052913234&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-23217-6_10
DO - 10.1007/978-3-642-23217-6_10
M3 - Conference contribution
AN - SCOPUS:80052913234
SN - 9783642232169
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 140
EP - 155
BT - CONCUR 2011 - Concurrency Theory - 22nd International Conference, Proceedings
T2 - 22nd Conference on Concurrency Theory, CONCUR 2011
Y2 - 6 September 2011 through 9 September 2011
ER -