  We introduce efficient algorithms for finding the $k$ shortest paths of a
weighted pushdown automaton (WPDA), a compact representation of a weighted set
of strings with potential applications in parsing and machine translation. Both
of our algorithms are derived from the same weighted deductive logic
description of the execution of a WPDA using different search strategies.
Experimental results show our Algorithm 2 adds very little overhead vs. the
single shortest path algorithm, even with a large $k$.
