3 papers
math.CO2007
The angel wins
Peter Gacs
The angel-devil game is played on an infinite two-dimensional ``chessboard''. The squares of the board are all white at the beginning. The players called angel and devil take turns…
math.PR2003
The Clairvoyant Demon Has a Hard Task
Peter Gacs
For some m \ge 4, let us color each column of the integer lattice L = Z^2 independently and uniformly into one of m colors. We do the same for the rows, independently from the colu…
cs.DC2001
Deterministic computations whose history is independent of the order of asynchronous updating
Peter Gacs
Consider a network of processors (sites) in which each site x has a finite set N(x) of neighbors. There is a transition function f that for each site x computes the next state ξ(x)…