Hi, I am a post-doctoral research associate with Patrick Totzke at the University of Liverpool. My research interests is in Theoretical Computer Science, specifically automata, games and logic.
Previously, I did my PhD at LaBRI, University of Bordeaux under the supervision of Anca Muscholl and Gabriele Puppis.
Before that, I did my Masters in Computer Science from Chennai Mathematical Institute(CMI) in 2017 and my Bachelors in Mathematics and Computer Science from CMI in 2015. My Master's thesis was supervised by B. Srivathsan.
Research Interests
My research focuses on topics in the intersection of Maths and Theoretical Computer Science, specifically Games, Automata Theory, Logic and Verification.
Currently, I am working on problems in algorithmic game theory as part of the EPSRC project "The cost of winning strategies".
I have previously worked on Transducers during my PhD, and on Timed systems during my Masters.
Publications
The Power of Counting Steps in Quantitative Games (accepted at CONCUR 2024)
(With Rasmus Ibsen-Jensen, David Purser, Patrick Totzke and Pierre Vandenhove) [arxiv]
Bounded-memory Strategies in Partial-Information Games (accepted at LICS 2024)
(With Rasmus Ibsen-Jensen and Patrick Totzke) [arxiv]
Parity Games on Temporal Graphs (FoSSaCS 2024)
(With Pete Austin and Patrick Totzke) [arxiv] [conference]
History-deterministic Vector Addition Systems (CONCUR 2023)
(With David Purser and Patrick Totzke) [arxiv][conference]
History-deterministic Timed Automata (to appear in LMCS special issue)
(With Thomas Henzinger, Karoliina Lehtinen, Sven Schewe and Patrick Totzke) [arxiv]
History-deterministic Timed Automata are Not Determinizable (RP 2022)
(With Thomas Henzinger, Karoliina Lehtinen, Sven Schewe and Patrick Totzke) [pdf][conference]
One-way Resynchronizability of Word Transducers (FoSSaCS 2021)
(With Krishna S., Anca Muscholl and Gabriele Puppis) [arxiv] [conference] [talk recording]
On Synthesis of Resynchronizers for Transducers (MFCS 2019)
(With Krishna S., Anca Muscholl, Vincent Penelle and Gabriele Puppis) [arxiv] [conference]
Origin-Equivalence of Two-Way Word Transducers Is in PSPACE (FSTTCS 2018)
(With Anca Muscholl, Vincent Penelle and Gabriele Puppis) [arxiv] [conference]
On Decision Problems on Word Transducers with Origin Semantics (Ph.D. Thesis)
(Supervisors: Anca Muscholl and Gabriele Puppis) [Dissertation]
Links
Theoretical Computer Science group at Liverpool
Indo-French ReLaX project
RATIO team at LaBRI, Bordeaux
Contact
email address: sougata <dot> bose <at> liverpool <dot> ac <dot> uk
Office no 211, Ashton Building
Department of Computer Science, University of Liverpool, Liverpool, L69 3BX, UK