Counting paths in pebbled mountain ranges

context-free languages DCFL can be accepted in polynomial time using
only log-squared space. In 1980, Kurt Mehlhorn defined input-driven
deterministic pushdown automata, and, using a strategy for pebbling
mountain ranges, improved the space bound for this subclass. A series
of subsequent results finally placed acceptance of such languages,
even with nondeterminism, in the complexity class NC^1 (equivalently,
alternating log time). Today such automata are called visible pushdown
automata VPA, and have found new applications in verification and XML
parsing.

We investigate the complexity of counting paths in (nondeterministic)
VPA. We show that this is no harder than accepting a fixed DCFL. In
this talk I will describe our counting algorithm.

This is joint work with Nutan Limaye.