Bi-Weekly Talk: Sebastian Junges und Dennis Fischer

Mittwoch, 25.07.2018, 10.15 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10

 

Vortragende: Sebastian Junges und Dennis Fischer

 

Sebastian Junges: Finite-state Controllers of POMDPs via Parameter Synthesis

We study finite-state controllers (FSCs) for partially observable Markov decision processes (POMDPs) that are provably correct with respect to given specifications. The key insight is that computing (randomised) FSCs on POMDPs is equivalent to (and computationally as hard as) synthesis for parametric Markov chains (pMCs). This correspondence enables using black-box techniques to compute correct-by-construction FSCs for POMDPs for a wide range of properties. Our experimental evaluation on POMDP problems shows comparable performance to well-known POMDP solvers. 

 

Application talk by Dennis Fischer: The conflict free coloring problem on planar graphs

In this talk I will introduce the conflict free coloring problem on graphs which is a coloring problem that is connected to frequency assignment in a network. I briefly talk about the currently known complexity results on planar graphs and present some of the results I got working on my master thesis. I present new NP-completeness proofs for planar graphs that show that all four variants of neighborhood coloring are NP-hard for less than 4 colors. I will also present a constant upper bound of 5 for open neighborhood coloring where no such bound was known before. I will also give an outlook about open problems in this area and extensions which are currently unexplored.