171 citations · 1.1k across the 134 of their papers we have counts for
13 papers · 1 filter
Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter
Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger +1
A model of computation that is widely used in the formal analysis of reactive systems is symbolic algorithms. In this model the access to the input graph is restricted to consist o…
Sensor Synthesis for POMDPs with Reachability Objectives
Krishnendu Chatterjee, Martin Chmelik, Ufuk Topcu
Partially observable Markov decision processes (POMDPs) are widely used in probabilistic planning problems in which an agent interacts with an environment using noisy and imprecise…
Lexicographic Ranking Supermartingales: An Efficient Approach to Termination of Probabilistic Programs
Sheshansh Agrawal, Krishnendu Chatterjee, Petr Novotný
Probabilistic programs extend classical imperative programs with real-valued random variables and random branching. The most basic liveness property for such programs is the termin…
Efficient Algorithms for Checking Fast Termination in VASS
Tomáš Brázdil, Krishnendu Chatterjee, Antonín Kučera +2
Vector Addition Systems with States (VASS) consists of a finite state space equipped with d counters, where in each transition every counter is incremented, decremented, or left un…
Bidirectional Nested Weighted Automata
Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop
Nested weighted automata (NWA) present a robust and convenient automata-theoretic formalism for quantitative specifications. Previous works have considered NWA that processed input…
Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Martin A. Nowak
Evolutionary graph theory studies the evolutionary dynamics in a population structure given as a connected graph. Each node of the graph represents an individual of the population,…