20 citations · 62 across the 23 of their papers we have counts for
3 papers · 1 filter
Simplified Game of Life: Algorithms and Complexity
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker +1
Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A…
Optimal and Perfectly Parallel Algorithms for On-demand Data-flow Analysis
Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen +1
Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointer…
One-Clock Priced Timed Games are PSPACE-hard
John Fearnley, Rasmus Ibsen-Jensen, Rahul Savani
The main result of this paper is that computing the value of a one-clock priced timed game (OCPTG) is PSPACE-hard. Along the way, we provide a family of OCPTGs that have an exponen…