125 citations · 284 across the 20 of their papers we have counts for
7 papers · 1 filter
Stable Multi-Level Monotonic Eroders
Péter Gács, Ilkka Törmä
Eroders are monotonic cellular automata with a linearly ordered state set that eventually wipe out any finite island of nonzero states. One-dimensional eroders were studied by Gal'…
Clairvoyant embedding in one dimension
Peter Gacs
Let v, w be infinite 0-1 sequences, and m a positive integer. We say that w is m-embeddable in v, if there exists an increasing sequence n_{i} of integers with n_{0}=0, such that 0…
Randomness on Computable Probability Spaces - A Dynamical Point of View
Peter Gacs, Mathieu Hoyrup, Cristobal Rojas
We extend the notion of randomness (in the version introduced by Schnorr) to computable Probability Spaces and compare it to a dynamical notion of randomness: typicality. Roughly,…
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…
Clairvoyant scheduling of random walks
Peter Gacs
Two infinite walks on the same finite graph are called compatible if it is possible to introduce delays into them in such a way that they never collide. Years ago, Peter Winkler as…
Compatible sequences and a slow Winkler percolation
Peter Gacs
Two infinite 0-1 sequences are called compatible when it is possible to cast out 0's from both in such a way that they become complementary to each other. Answering a question of P…
Reliable Cellular Automata with Self-Organization
Peter Gacs
In a probabilistic cellular automaton in which all local transitions have positive probability, the problem of keeping a bit of information indefinitely is nontrivial, even in an i…