Computer Science Logic and 8th Kurt Gödel Colloquium
Lukasz Krzeszczakowski: Pebble games on trees
Welcome and News
Host Institutions
Calls and Deadlines
Social Program
Location and Venue
Colocated Events
Authors' instructions
Print current pagePrint this page
It is well known that two structures A and B are indistinguishable by sentences of the infinitary logic with k variables L^k_{\infty\omega} iff Duplicator wins the Barwise game on A and B with k pebbles. The complexity of the problem who wins the game is in general unknown if k is a part of the input. We prove that the problem is in PTIME for some special classes of structures such as finite directed trees and infinite regular trees. More specifically, we show an algorithm running in time log (k) ( |A| + |B| )^{O(1)} .

The algorithm for regular trees is based on a characterization of the winning pairs (A,B) which is valid also for a more general case of (potentially infinite) rooted trees.
© 2002-2003 Kurt Gödel Society, Norbert Preining. 2003-06-04 Valid HTML 4.01! Valid CSS! Debian