Show simple item record

dc.contributor.authorKfoury, A.J.en_US
dc.contributor.authorStolboushkin, A.P.en_US
dc.date.accessioned2011-10-20T04:37:41Z
dc.date.available2011-10-20T04:37:41Z
dc.date.issued1996-08-15en_US
dc.identifier.citationKfoury, A.J.; Stolboushkin, A.P.. "An Infinite Pebble Game and Applications", Technical Report BUCS-1996-020, Computer Science Department, Boston University, August 15, 1996. [Available from: http://hdl.handle.net/2144/1596]en_US
dc.identifier.urihttps://hdl.handle.net/2144/1596
dc.description.abstractWe 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.en_US
dc.description.sponsorshipNational Science Foundation (CCR-9417382, CCR-9403809)en_US
dc.language.isoen_USen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-1996-020en_US
dc.titleAn Infinite Pebble Game and Applicationsen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record