An Infinite Pebble Game and Applications
Assaf J. Kfoury, Alexei P. Stolboushkin · Information and Computation · 1997
We generalize the pebble game to infinite directed acyclic graphs and use this generalization to give new and shorter proofs of the following well-known results: (1) that unbounded memory increases the power of logics of programs, and (2) that there exists a context-free grammar with infinite index.