1 citations · 2 across the 8 of their papers we have counts for
11 papers
Generalised Reachability Games
Sougata Bose, Nathanael Fijalkow, Daniel Hausmann +4
We study two-player zero-sum turn-based games played on graphs with multiple reachability objectives called generalised reachability games. In classic reachability games the goal o…
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…
Temporal Explorability Games
Pete Austin, Nicolas Mazzocchi, Sougata Bose +1
Temporal graphs extend ordinary graphs with discrete time that affects the availability of edges. We consider solving games played on temporal graphs where one player aims to explo…
The Power of Counting Steps in Quantitative Games
Sougata Bose, Rasmus Ibsen-Jensen, David Purser +2
We study deterministic games of infinite duration played on graphs and focus on the strategy complexity of quantitative objectives. Such games are known to admit optimal memoryless…
Bounded-Memory Strategies in Partial-Information Games
Sougata Bose, Rasmus Ibsen-Jensen, Patrick Totzke
We study the computational complexity of solving stochastic games with mean-payoff objectives. Instead of identifying special classes in which simple strategies are sufficient to p…
Parity Games on Temporal Graphs
Pete Austin, Sougata Bose, Patrick Totzke
Temporal graphs are a popular modelling mechanism for dynamic complex systems that extend ordinary graphs with discrete time. Simply put, time progresses one unit per step and the…
History-deterministic Vector Addition Systems
Sougata Bose, David Purser, Patrick Totzke
We consider history-determinism, a restricted form of non-determinism, for Vector Addition Systems with States (VASS) when used as acceptors to recognise languages of finite words.…
History-deterministic Timed Automata
Sougata Bose, Thomas A. Henzinger, Karoliina Lehtinen +2
We explore the notion of history-determinism in the context of timed automata (TA) over infinite timed words. History-deterministic (HD) automata are those in which nondeterminism…
One-way resynchronizability of word transducers
Sougata Bose, S. N. Krishna, Anca Muscholl +1
The origin semantics for transducers was proposed in 2014, and led to various characterizations and decidability results that are in contrast with the classical semantics. In this…
On Synthesis of Resynchronizers for Transducers
Sougata Bose, Shankara Narayanan Krishna, Anca Muscholl +2
We study two formalisms that allow to compare transducers over words under origin semantics: rational and regular resynchronizers, and show that the former are captured by the latt…
Origin-equivalence of two-way word transducers is in PSPACE
Sougata Bose, Anca Muscholl, Vincent Penelle +1
We consider equivalence and containment problems for word transductions. These problems are known to be undecidable when the transductions are relations between words realized by n…