9 papers
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…
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…
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…
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…
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…