License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2015.184
URN: urn:nbn:de:0030-drops-53789
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5378/
Go to the corresponding LIPIcs Volume Portal

Forejt, Vojtech ; Krcal, Jan

On Frequency LTL in Probabilistic Systems

pdf-format:
18.pdf (0.5 MB)

Abstract

We study frequency linear-time temporal logic (fLTL) which extends the linear-time temporal logic (LTL) with a path operator G^p expressing that on a path, certain formula holds with at least a given frequency p, thus relaxing the semantics of the usual G operator of LTL. Such logic is particularly useful in probabilistic systems, where some undesirable events such as random failures may occur and are acceptable if they are rare enough. Frequency-related extensions of LTL have been previously studied by several authors, where mostly the logic is equipped with an extended "until" and "globally" operator, leading to undecidability of most interesting problems.

For the variant we study, we are able to establish fundamental decidability results. We show that for Markov chains, the problem of computing the probability with which a given fLTL formula holds has the same complexity as the analogous problem for LTL. We also show that for Markov decision processes the problem becomes more delicate, but when restricting the frequency bound p to be 1 and negations not to be outside any G^p operator, we can compute the maximum probability of satisfying the fLTL formula. This can be again performed with the same time complexity as for the ordinary LTL formulas.

BibTeX - Entry

@InProceedings{forejt_et_al:LIPIcs:2015:5378,
  author =	{Vojtech Forejt and Jan Krcal},
  title =	{{On Frequency LTL in Probabilistic Systems}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{184--197},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Luca Aceto and David de Frutos Escrig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5378},
  URN =		{urn:nbn:de:0030-drops-53789},
  doi =		{10.4230/LIPIcs.CONCUR.2015.184},
  annote =	{Keywords: Markov chains, Markov decision processes, LTL, controller synthesis}
}

Keywords: Markov chains, Markov decision processes, LTL, controller synthesis
Collection: 26th International Conference on Concurrency Theory (CONCUR 2015)
Issue Date: 2015
Date of publication: 26.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI