License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2021.6
URN: urn:nbn:de:0030-drops-143834
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14383/
Go to the corresponding LIPIcs Volume Portal

Kiefer, Stefan ; Semukhin, Pavel ; Widdershoven, Cas

Linear-Time Model Checking Branching Processes

pdf-format:
LIPIcs-CONCUR-2021-6.pdf (0.6 MB)

Abstract

(Multi-type) branching processes are a natural and well-studied model for generating random infinite trees. Branching processes feature both nondeterministic and probabilistic branching, generalizing both transition systems and Markov chains (but not generally Markov decision processes). We study the complexity of model checking branching processes against linear-time omega-regular specifications: is it the case almost surely that every branch of a tree randomly generated by the branching process satisfies the omega-regular specification? The main result is that for LTL specifications this problem is in PSPACE, subsuming classical results for transition systems and Markov chains, respectively. The underlying general model-checking algorithm is based on the automata-theoretic approach, using unambiguous Büchi automata.

BibTeX - Entry

@InProceedings{kiefer_et_al:LIPIcs.CONCUR.2021.6,
  author =	{Kiefer, Stefan and Semukhin, Pavel and Widdershoven, Cas},
  title =	{{Linear-Time Model Checking Branching Processes}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14383},
  URN =		{urn:nbn:de:0030-drops-143834},
  doi =		{10.4230/LIPIcs.CONCUR.2021.6},
  annote =	{Keywords: model checking, Markov chains, branching processes, automata, computational complexity}
}

Keywords: model checking, Markov chains, branching processes, automata, computational complexity
Collection: 32nd International Conference on Concurrency Theory (CONCUR 2021)
Issue Date: 2021
Date of publication: 13.08.2021

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