3 citations · 8 across the 13 of their papers we have counts for
6 papers · 1 filter
Decoupled Planning for Multiple Omega-Regular Objectives
Guy Avni, Thomas A. Henzinger, Kaushik Mallik +2
We study the problem of generating paths on a graph that satisfy a collection of ω-regular objectives. We propose a decoupled framework in which each objective is assigned to an in…
History-Deterministic Büchi Automata are Succinct
Antonio Casares, Keya Prakash, K. S. Thejaswini
We describe a history-deterministic Büchi automaton that has strictly less states than every language-equivalent deterministic Büchi automaton. This solves a problem that had been…
Resolving Nondeterminism with Randomness
Thomas A. Henzinger, Keya Prakash, K. S. Thejaswini
In automata theory, while determinisation provides a standard route to solving many common problems in automata theory, some weak forms of nondeterminism can be dealt with in some…
Simple and tight complexity lower bounds for solving Rabin games
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk +2
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time , where $k…
On History-Deterministic One-Counter Nets
Keya Prakash, K. S. Thejaswini
We consider the model of history-deterministic one-counter nets (OCNs). History-determinism is a property of transition systems that allows for a limited kind of non-determinism wh…
Adaptive Synchronisation of Pushdown Automata
A. R. Balasubramanian, K. S. Thejaswini
We introduce the notion of adaptive synchronisation for pushdown automata, in which there is an external observer who has no knowledge about the current state of the pushdown autom…