10.46298/dmtcs.5943
Fülöp, Zoltán
Zoltán
Fülöp
Kószó, Dávid
Dávid
Kószó
Vogler, Heiko
Heiko
Vogler
Crisp-determinization of weighted tree automata over strong bimonoids
episciences.org
2021
Computer Science - Formal Languages and Automata Theory
contact@episciences.org
episciences.org
2019-12-06T13:33:22+01:00
2021-08-23T23:08:41+02:00
2021-06-15
eng
Journal article
https://dmtcs.episciences.org/5943
arXiv:1912.02660
1365-8050
PDF
1
Discrete Mathematics & Theoretical Computer Science ; vol. 23 no. 1 ; Automata, Logic and Semantics ; 1365-8050
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.