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

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

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

OriginalspracheEnglisch
Seiten (von - bis)118-143
Seitenumfang26
FachzeitschriftTheoretical computer science : the journal of the EATCS
Jahrgang919
AusgabenummerC
PublikationsstatusVeröffentlicht - 5 Juni 2022
Peer-Review-StatusJa

Externe IDs

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

Schlagworte

Schlagwörter

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