Abstract
Weighted tree automata (WTA) extend classical weighted automata
(WA) to the non-linear structure of trees. The expressive power
of WA with varying degrees of ambiguity has been extensively
studied. Unambiguous, finitely ambiguous, and polynomially
ambiguous WA over the tropical (as well as the arctic) semiring
strictly increase in expressive power. The recently developed
pumping results of Mazowiecki and Riveros (STACS 2018) are
lifted to trees in order to achieve the same strict hierarchy
for WTA over the tropical (as well as the arctic) semiring.
Users
Please
log in to take part in the discussion (add own reviews or comments).
