Crisp-determinization of weighted tree automata over strong bimonoids

Fülöp, Zoltán ; Kószó, Dávid ; Vogler, Heiko

Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 1.

Résumé

We consider weighted tree automata (wta) over strong bimonoids and their initial algebra semantics and their run semantics. There are wta for which these semantics are different; however, for bottom-up deterministic wta and for wta over semirings, the difference vanishes. A wta is crisp-deterministic if it is bottom-up deterministic and each transition is weighted by one of the unit elements of the strong bimonoid. We prove that the class of weighted tree languages recognized by crisp-deterministic wta is the same as the class of recognizable step mappings. Moreover, we investigate the following two crisp-determinization problems: for a given wta ${\cal A}$, (a) does there exist a crisp-deterministic wta which computes the initial algebra semantics of ${\cal A}$ and (b) does there exist a crisp-deterministic wta which computes the run semantics of ${\cal A}$? We show that the finiteness of the Nerode algebra ${\cal N}({\cal A})$ of ${\cal A}$ implies a positive answer for (a), and that the finite order property of ${\cal A}$ implies a positive answer for (b). We show a sufficient condition which guarantees the finiteness of ${\cal N}({\cal A})$ and a sufficient condition which guarantees the finite order property of ${\cal A}$. Also, we provide an algorithm for the construction of the crisp-deterministic wta according to (a) if ${\cal N}({\cal A})$ is finite, and similarly for (b) if ${\cal A}$ has finite order property. We prove that it is undecidable whether an arbitrary wta ${\cal A}$ is crisp-determinizable. We also prove that both, the finiteness of ${\cal N}({\cal A})$ and the finite order property of ${\cal A}$ are undecidable.

Détail

DOI : 10.46298/dmtcs.5943

Classification : 20M35, 68Q70