The Stochastic Arrival Problem

Thomas Webster

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study a new modification of the Arrival problem, which allows for nodes that exhibit random as well as controlled behaviour, in addition to switching nodes. We study the computational complexity of these extensions, building on existing work on Reachability Switching Games. In particular, we show for versions of the arrival problem involving just switching and random nodes it is PP-hard to decide if their value is greater than a half and we give a PSPACE decision algorithm.
Original languageEnglish
Title of host publicationProceedings of the 16th International Conference on Reachability Problems
EditorsAnthony W. Lin, Georg Zetzsche, Igor Potapov
PublisherSpringer, Cham
Pages93-107
Number of pages15
ISBN (Electronic)978-3-031-19135-0
ISBN (Print)978-3-031-19134-3
DOIs
Publication statusPublished - 12 Oct 2022
EventThe 16th International Conference on Reachability Problems, 2022 - Kaiserslautern, Germany
Duration: 17 Oct 202219 Oct 2022
Conference number: 16
https://rp2022.mpi-sws.org/submission.html

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
Volume13608
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceThe 16th International Conference on Reachability Problems, 2022
Abbreviated titleRP 2022
Country/TerritoryGermany
CityKaiserslautern
Period17/10/2219/10/22
Internet address

Keywords

  • Arrival
  • Markov Chains
  • Reachability Switching Games
  • MDPs
  • Simple Stochastic Games

Fingerprint

Dive into the research topics of 'The Stochastic Arrival Problem'. Together they form a unique fingerprint.

Cite this