episciences.org_5943_1639049823
1639049823
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
06
15
2021
vol. 23 no. 1
Automata, Logic and Semantics
Crisp-determinization of weighted tree automata over strong bimonoids
Zoltán
Fülöp
Dávid
Kószó
Heiko
Vogler
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.
06
15
2021
5943
arXiv:1912.02660
10.46298/dmtcs.5943
https://dmtcs.episciences.org/5943