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

Research output: Contribution to journalResearch articleContributedpeer-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 languageEnglish
Pages (from-to)118-143
Number of pages26
JournalTheoretical computer science : the journal of the EATCS
Volume919
Issue numberC
Publication statusPublished - 5 Jun 2022
Peer-reviewedYes

External IDs

Scopus 85128189967
Mendeley 401aed30-59b4-36df-a7e8-1da06ea92979

Keywords

Keywords

  • Decidability, Finite-image property, Past-finite strong bimonoid, Semiring, Strong bimonoid, Weighted tree automaton