Two dynamic programming algorithms for which interpreted pebbling helps

We consider extensions of one-person and two-person pebble games that take into account the types of the gates of the circuits on which the games are played. A simple relationship is established between the extended games and the corresponding original games. This is useful in showing that the extended games allow more efficient pebbling than the original games on certain natural circuits for problems such as context-free language recognition and transitive closure of directed graphs.

Authors

• H. Venkateswaran

Keywords

No keywords are indexed for this paper.