8 citations · 18 across the 21 of their papers we have counts for
30 papers
Set Automata and Limits of Decidability of Two-Variable Logic on Data Words
Shibashis Guha, Amaldev Manuel, S P Rishal
We extend the two-variable logic on data words with guarded regular binary predicates of the form that is true if positions and are in the same class a…
Sure-almost-sure and Sure-limit-sure Window Mean Payoff in Markov Decision Processes
Pranshu Gaba, Shibashis Guha
Given rationals and , the sure-almost-sure problem for a threshold Boolean objective in a Markov decision process (MDP) asks if one can simultaneously ensure that all ou…
Algorithm and Strategy Construction for Sure-Almost-Sure Stochastic Parity Games
Laurent Doyen, Shibashis Guha
We consider turn-based stochastic two-player games with a combination of a parity condition that must hold surely, that is in all possible outcomes, and of a parity condition that…
Scalable Learning of One-Counter Automata via State-Merging Algorithms
Shibashis Guha, Anirban Majumdar, Prince Mathew +1
We propose One-counter Positive Negative Inference (OPNI), a passive learning algorithm for deterministic real-time one-counter automata (DROCA). Inspired by the RPNI algorithm for…
Optimising expectation with guarantees for window mean payoff in Markov decision processes
Pranshu Gaba, Shibashis Guha
The window mean-payoff objective strengthens the classical mean-payoff objective by computing the mean-payoff over a finite window that slides along an infinite path. Two variants…
Expectation in Stochastic Games with Prefix-independent Objectives
Laurent Doyen, Pranshu Gaba, Shibashis Guha
Stochastic two-player games model systems with an environment that is both adversarial and stochastic. In this paper, we study the expected value of bounded quantitative prefix-ind…
Set Augmented Finite Automata over Infinite Alphabets
Ansuman Banerjee, Kingshuk Chatterjee, Shibashis Guha
A data language is a set of finite words defined on an infinite alphabet. Data languages are used to express properties associated with data values (domain defined over a countably…
A Game of Pawns
Guy Avni, Pranav Ghorpade, Shibashis Guha
We introduce and study pawn games, a class of two-player zero-sum turn-based graph games. A turn-based graph game proceeds by placing a token on an initial vertex, and whoever cont…
Stochastic Window Mean-Payoff Games
Laurent Doyen, Pranshu Gaba, Shibashis Guha
Stochastic two-player games model systems with an environment that is both adversarial and stochastic. The adversarial part of the environment is modeled by a player (Player 2) who…
Reinforcement Learning for Omega-Regular Specifications on Continuous-Time MDP
Amin Falah, Shibashis Guha, Ashutosh Trivedi
Continuous-time Markov decision processes (CTMDPs) are canonical models to express sequential decision-making under dense-time and stochastic environments. When the stochastic evol…
History-deterministic Parikh Automata
Enzo Erlich, Mario Grobler, Shibashis Guha +3
Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run. Thereby, they preserve many of the desirable…
Parikh Automata over Infinite Words
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen +1
Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run, thereby preserving many of the desirable alg…
PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP
Chaitanya Agarwal, Shibashis Guha, Jan Křetínský +1
Markov decision processes (MDP) and continuous-time MDP (CTMDP) are the fundamental models for non-deterministic systems with probabilistic uncertainty. Mean payoff (a.k.a. long-ru…
Strategy Synthesis for Global Window PCTL
Benjamin Bordais, Damien Busatto-Gaston, Shibashis Guha +1
Given a Markov decision process (MDP) and a formula , the strategy synthesis problem asks if there exists a strategy s.t. the resulting Markov chain satisfies …
A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen +1
We study the expressiveness and succinctness of history-deterministic pushdown automata (HD-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved…
Fragility and Robustness in Mean-Payoff Adversarial Stackelberg Games
Mrudula Balachander, Shibashis Guha, Jean-François Raskin
Two-player mean-payoff Stackelberg games are nonzero-sum infinite duration games played on a bi-weighted graph by Leader (Player 0) and Follower (Player 1). Such games are played s…
Safe Learning for Near Optimal Scheduling
Damien Busatto-Gaston, Debraj Chakraborty, Shibashis Guha +2
In this paper, we investigate the combination of synthesis, model-based learning, and online sampling techniques to obtain safe and near-optimal schedulers for a preemptible task s…
Mixing Probabilistic and non-Probabilistic Objectives in Markov Decision Processes
Raphaël Berthon, Shibashis Guha, Jean-François Raskin
In this paper, we consider algorithms to decide the existence of strategies in MDPs for Boolean combinations of objectives. These objectives are omega-regular properties that need…
Alternating Tree Automata with Qualitative Semantics
Raphaël Berthon, Nathanaël Fijalkow, Emmanuel Filiot +7
We study alternating automata with qualitative semantics over infinite binary trees: alternation means that two opposing players construct a decoration of the input tree called a r…
Two-way Parikh Automata
Emmanuel Filiot, Shibashis Guha, Nicolas Mazzocchi
Parikh automata extend automata with counters whose values can only be tested at the end of the computation, with respect to membership into a semi-linear set. Parikh automata have…
Monadic Second-Order Logic with Path-Measure Quantifier is Undecidable
Raphaël Berthon, Emmanuel Filiot, Shibashis Guha +5
We prove that the theory of Monadic Second-Order logic (MSO) of the infinite binary tree extended with qualitative path-measure quantifier is undecidable. This quantifier says that…
Expected Window Mean-Payoff
Benjamin Bordais, Shibashis Guha, Jean-François Raskin
In the window mean-payoff objective, given an infinite path, instead of considering a long run average, we consider the minimum payoff that can be ensured at every position of the…
Timed Network Games with Clocks
Guy Avni, Shibashis Guha, Orna Kupferman
Network games are widely used as a model for selfish resource-allocation problems. In the classical model, each player selects a path connecting her source and target vertices. The…
Mean-Payoff Games on Timed Automata
Shibashis Guha, Marcin Jurdzinski, Krishna S. +1
Mean-payoff games on timed automata are played on the infinite weighted graph of configurations of priced timed automata between two players, Player Min and Player Max, by moving a…