Crisp-determinization of weighted tree automata over strong bimonoids
Zoltán Fülöp, Dávid Kószó, Heiko Vogler · arXiv (Cornell University) · 2019
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 A, (a) is there a crisp-deterministic wta which computes the initial algebra semantics of A and (b) is there a crisp-deterministic wta which computes the run semantics of A? We show that the finiteness of the Nerode algebra N (A) of A implies a positive answer for (a), and that the finite order property of A implies a positive answer for (b).We show a sufficient condition which guarantees the finiteness of N (A) and a sufficient condition which guarantees the finite order property of A. Also, we provide an algorithm for the construction of the crisp-deterministic wta according to (a) if N (A) is finite, and similarly for (b) if A has finite order property.We prove that it is undecidable whether an arbitrary wta A is crisp-determinizable.We also prove that both, the finiteness of N (A) and the finite order property of A are undecidable.