Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids

Abstract

We consider weighted tree automata over strong bimonoids (for short: wta). A wta $\mathcal{A}$ has the finite-image property if its recognized weighted tree language $[[\mathcal{A}]]$ has finite image; moreover, $\mathcal{A}$ has the preimage property if the preimage under $[[\mathcal{A}]]$ of each element of the underlying strong bimonoid is a recognizable tree language. For each wta $\mathcal{A}$ over a past-finite monotonic strong bimonoid we prove the following results. In terms of $\mathcal{A}$'s structural properties, we characterize whether it has the finite-image property. We characterize those past-finite monotonic strong bimonoids such that for each wta $\mathcal{A}$ it is decidable whether $\mathcal{A}$ has the finite-image property. In particular, the finite-image property is decidable for wta over past-finite monotonic semirings. Moreover, we prove that $\mathcal{A}$ has the preimage property. All our results also hold for weighted string automata.

42 pages, 4 figures, 1 algorithm