Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids.
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
Abstract
We consider weighted tree automata over strong bimonoids (for short: wta). A wta A has the finite-image property if its recognized weighted tree language 〚A〛 has finite image; moreover, A has the preimage property if the preimage under 〚A〛 of each element of the underlying strong bimonoid is a recognizable tree language. For each wta A over a past-finite monotonic strong bimonoid we prove the following results. In terms of 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 A it is decidable whether 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 A has the preimage property. All our results also hold for weighted string automata.
Details
Original language | English |
---|---|
Pages (from-to) | 118-143 |
Number of pages | 26 |
Journal | Theoretical computer science : the journal of the EATCS |
Volume | 919 |
Issue number | C |
Publication status | Published - 5 Jun 2022 |
Peer-reviewed | Yes |
External IDs
Scopus | 85128189967 |
---|---|
Mendeley | 401aed30-59b4-36df-a7e8-1da06ea92979 |
Keywords
ASJC Scopus subject areas
Keywords
- Decidability, Finite-image property, Past-finite strong bimonoid, Semiring, Strong bimonoid, Weighted tree automaton