Title: An Infinite Pebble Game and Applications
Authors: A.J. Kfoury, Computer Science, Boston University and A.P. Stolboushkin, Mathematics, UCLA
Date: August 15, 1996
Abstract:
We generalize the well-known pebble game to infinite dag's, and we
use this generalization to give new and shorter proofs of results in
different areas of computer science (as diverse as ``logic of programs''
and ``formal language theory''). Our applications here include a proof
of a theorem due to Salomaa, asserting the existence of a context-free
language with infinite index, and a proof of a theorem due to Tiuryn
and Erimbetov, asserting that unbounded memory increases the power of
logics of programs. The original proofs by Salomaa, Tiuryn, and Erimbetov,
are fairly technical. The proofs by Tiuryn and Erimbetov also involve
advanced techniques of model theory, namely, back-and-forth constructions
based on a variant of Ehrenfeucht-Fraisse games. By contrast, our proofs
are not only shorter, but also elementary. All we need is essentially
finite induction and, in the case of the Tiuryn-Erimbetov result, the
compactness and completeness of first-order logic.