6 papers
The Complexity of Games with Randomised Control
Sarvin Bahmani, Rasmus Ibsen-Jensen, Soumyajit Paul +5
We study the complexity of solving two-player infinite duration games played on a fixed finite graph, where the control of a node is not predetermined but rather assigned randomly.…
Good-for-MDP State Reduction for Stochastic LTL Planning
Christoph Weinhuber, Giuseppe De Giacomo, Yong Li +2
We study stochastic planning problems in Markov Decision Processes (MDPs) with goals specified in Linear Temporal Logic (LTL). The state-of-the-art approach transforms LTL formulas…
Generalised Reachability Games Revisited
Sougata Bose, Daniel Hausmann, Soumyajit Paul +2
Classic reachability games on graphs are zero-sum games, where the goal of one player, Eve, is to visit a vertex from a given target set, and that of other player, Adam, is to prev…
Efficient Learning of Weak Deterministic Büchi Automata
Mona Alluwayma, Yong Li, Sven Schewe +1
We present an efficient Angluin-style learning algorithm for weak deterministic Büchi automata (wDBAs). Different to ordinary deterministic Büchi and co-Büchi automata, wDBAs have…
Saturation Problems for Families of Automata
León Bohn, Yong Li, Christof Löding +1
Families of deterministic finite automata (FDFA) represent regular -languages through their ultimately periodic words (UP-words). An FDFA accepts pairs of words, where the first…
Solving MDPs with LTLf+ and PPLTL+ Temporal Objectives
Giuseppe De Giacomo, Yong Li, Sven Schewe +2
The temporal logics LTLf+ and PPLTL+ have recently been proposed to express objectives over infinite traces. These logics are appealing because they match the expressive power of L…