Biblio Discovery — Demo Discovery Service

44 results for "Krishnendu Chatterjee"

Showing 1–20 · 0.42 seconds · RSS

  1. Journal Article Full text

    A reduction from parity games to simple stochastic games

    Krishnendu Chatterjee; Nathanaël Fijalkow

    Electronic Proceedings in Theoretical Computer Science, Vol. 54 No. Proc. GandALF 2011 · 2011 · English · DOAJ

    Games on graphs provide a natural model for reactive non-terminating systems. In such games, the interaction of two players on an arena results in an infinite path that describes a run of the system. Different settings are used to model various open systems in computer science, as for instance…

  2. Journal Article

    Stochastic Processes with Expected Stopping Time

    Krishnendu Chatterjee; Laurent Doyen

    Logical Methods in Computer Science, Vol. Volume 20 No. ue 4 · 2024 · English · DOAJ Scopus

    Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward…

  3. Journal Article Full text

    Discounting in Games across Time Scales

    Krishnendu Chatterjee; Rupak Majumdar

    Electronic Proceedings in Theoretical Computer Science, Vol. 25 No. Proc. GANDALF 2010 · 2010 · English · DOAJ

    We introduce two-level discounted games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted game and the lower level game is an undiscounted reachability game. Two-level games model hierarchical and sequential decision making under uncertainty…

  4. Journal Article Full text

    Evolution of Decisions in Population Games with Sequentially Searching Individuals

    Tadeas Priklopil; Krishnendu Chatterjee

    Games, Vol. 6 No. 4 · 2015 · English · DOAJ Scopus

    In many social situations, individuals endeavor to find the single best possible partner, but are constrained to evaluate the candidates in sequence. Examples include the search for mates, economic partnerships, or any other long-term ties where the choice to interact involves two parties…

  5. Journal Article

    Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes

    Krishnendu Chatterjee; Zuzana Křetínská; Jan Křetínský

    Logical Methods in Computer Science, Vol. Volume 13 No. ue 2 · 2017 · English · DOAJ Scopus

    We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize…

  6. Journal Article

    Improved Algorithms for Parity and Streett objectives

    Krishnendu Chatterjee; Monika Henzinger; Veronika Loitzenbauer

    Logical Methods in Computer Science, Vol. Volume 13 No. ue 3 · 2017 · English · DOAJ Scopus

    The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems…

  7. Journal Article

    Quantitative Automata under Probabilistic Semantics

    Krishnendu Chatterjee; Thomas A. Henzinger; Jan Otop

    Logical Methods in Computer Science, Vol. Volume 15 No. ue 3 · 2019 · English · DOAJ Scopus

    Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor…

  8. Journal Article

    Expressiveness and Closure Properties for Quantitative Languages

    Krishnendu Chatterjee; Laurent Doyen; Thomas A Henzinger

    Logical Methods in Computer Science, Vol. Volume 6 No. ue 3 · 2010 · English · DOAJ Scopus

    Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages~$L$ that assign to each word~$w$ a real number~$L(w)$. In the case of infinite words, the value of a run is naturally computed as the maximum, limsup, liminf, limit-average…

  9. Journal Article Full text

    Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating

    Jakub Svoboda; Soham Joshi; Josef Tkadlec et al.

    PLOS Computational Biology, Vol. 20 No. 3 · 2024 · English · PLOS Scopus

    Populations evolve by accumulating advantageous mutations. Every population has some spatial structure that can be modeled by an underlying network. The network then influences the probability that new advantageous mutations fixate. Amplifiers of selection are networks that increase the fixation…

    Also available at: DOAJ

  10. Journal Article Full text

    The Time Scale of Evolutionary Innovation

    Krishnendu Chatterjee; Andreas Pavlogiannis; Ben Adlam et al.

    PLoS Computational Biology, Vol. 10 No. 9 · 2014 · English · PLOS Scopus

    A fundamental question in biology is the following: what is the time scale that is needed for evolutionary innovations? There are many results that characterize single steps in terms of the fixation time of new mutants arising in populations of certain size and structure. But here we ask a…

  11. Journal Article Full text

    The Moran process on 2-chromatic graphs

    Kamran Kaveh; Alex McAvoy; Krishnendu Chatterjee et al.

    PLOS Computational Biology, Vol. 16 No. 11 · 2020 · English · PLOS Scopus

    Resources are rarely distributed uniformly within a population. Heterogeneity in the concentration of a drug, the quality of breeding sites, or wealth can all affect evolutionary dynamics. In this study, we represent a collection of properties affecting the fitness at a given location using a…

  12. Journal Article Full text

    Limits on amplifiers of natural selection under death-Birth updating

    Josef Tkadlec; Andreas Pavlogiannis; Krishnendu Chatterjee et al.

    PLOS Computational Biology, Vol. 16 No. 1 · 2020 · English · PLOS Scopus

    The fixation probability of a single mutant invading a population of residents is among the most widely-studied quantities in evolutionary dynamics. Amplifiers of natural selection are population structures that increase the fixation probability of advantageous mutants, compared to well-mixed…

    Also available at: DOAJ

  13. Journal Article Full text

    Direct reciprocity between individuals that use different strategy spaces

    Laura Schmid; Christian Hilbe; Krishnendu Chatterjee et al.

    PLOS Computational Biology, Vol. 18 No. 6 · 2022 · English · PLOS Scopus

    In repeated interactions, players can use strategies that respond to the outcome of previous rounds. Much of the existing literature on direct reciprocity assumes that all competing individuals use the same strategy space. Here, we study both learning and evolutionary dynamics of players that…

  14. Journal Article

    Quantitative assessment can stabilize indirect reciprocity under imperfect information

    Laura Schmid; Farbod Ekbatani; Christian Hilbe et al.

    Nature Communications, Vol. 14 No. 1 · 2023 · English · DOAJ Scopus

    Abstract The field of indirect reciprocity investigates how social norms can foster cooperation when individuals continuously monitor and assess each other’s social interactions. By adhering to certain social norms, cooperating individuals can improve their reputation and, in turn, receive benefits…

  15. Journal Article

    Timed Parity Games: Complexity and Robustness

    Krishnendu Chatterjee; Thomas A. Henzinger; Vinayak S. Prabhu

    Logical Methods in Computer Science, Vol. Volume 7 No. ue 4 · 2011 · English · DOAJ Scopus

    We consider two-player games played in real time on game structures with clocks where the objectives of players are described using parity conditions. The games are \emph{concurrent} in that at each turn, both players independently propose a time delay and an action, and the action with the shorter…

  16. Journal Article Full text

    Approximating the minimum cycle mean

    Krishnendu Chatterjee; Monika Henzinger; Sebastian Krinninger et al.

    Electronic Proceedings in Theoretical Computer Science, Vol. 119 No. Proc. GandALF 2013 · 2013 · English · DOAJ

    We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible in O(n^2) time to the…

  17. Journal Article

    The evolution of indirect reciprocity under action and assessment generosity

    Laura Schmid; Pouya Shati; Christian Hilbe et al.

    Scientific Reports, Vol. 11 No. 1 · 2021 · English · DOAJ Scopus

    Abstract Indirect reciprocity is a mechanism for the evolution of cooperation based on social norms. This mechanism requires that individuals in a population observe and judge each other’s behaviors. Individuals with a good reputation are more likely to receive help from others. Previous work…

  18. Journal Article Full text

    Mistakes can stabilise the dynamics of rock-paper-scissors games

    Maria Kleshnina; Sabrina S. Streipert; Jerzy A. Filar et al.

    PLOS Computational Biology, Vol. 17 No. 4 · 2021 · English · PLOS Scopus

    A game of rock-paper-scissors is an interesting example of an interaction where none of the pure strategies strictly dominates all others, leading to a cyclic pattern. In this work, we consider an unstable version of rock-paper-scissors dynamics and allow individuals to make behavioural mistakes…