Fixed-delay events in generalized semi-Markov processes revisited

Tomáš Brázdil, Jan Krčál, Jan Křetínský, Vojtěch Řehák

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationCONCUR 2011 - Concurrency Theory - 22nd International Conference, Proceedings
Pages140-155
Number of pages16
DOIs
StatePublished - 2011
Event22nd Conference on Concurrency Theory, CONCUR 2011 - Aachen, Germany
Duration: 6 Sep 20119 Sep 2011

Publication series

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

Conference

Conference22nd Conference on Concurrency Theory, CONCUR 2011
Country/TerritoryGermany
CityAachen
Period6/09/119/09/11

Fingerprint

Dive into the research topics of 'Fixed-delay events in generalized semi-Markov processes revisited'. Together they form a unique fingerprint.

Cite this