Bi-Weekly Talk: Sebastian Junges and Dennis Fischer
Wednesday, 25.07.2018, 10:15 am
Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10
Speakers: Sebastian Junges and 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.