Title: Bidirectional Nested Weighted Automata,
Abstract: Nested weighted automata (NWA) present a robust and convenient
automata-theoretic formalism for quantitative specifications. Previous works
have considered NWA that processed input words only in the forward direction.
It is natural to allow the automata to process input words backwards as well,
for example, to measure the maximal or average time between a response and the
preceding request. We therefore introduce and study bidirectional NWA that can
process input words in both directions. First, we show that bidirectional NWA
can express interesting quantitative properties that are not expressible by
forward-only NWA. Second, for the fundamental decision problems of emptiness
and universality, we establish decidability and complexity results for the new
framework which match the best-known results for the special case of
forward-only NWA. Thus, for NWA, the increased expressiveness of
bidirectionality is achieved at no additional computational complexity. This is
in stark contrast to the unweighted case, where bidirectional finite automata
are no more expressive but exponentially more succinct than their forward-only
counterparts.