The generating power of weighted tree automata with initial algebra semantics
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910476126912512 |
|---|---|
| author | Droste, Manfred Fülöp, Zoltán Tepavčević, Andreja Vogler, Heiko |
| author_facet | Droste, Manfred Fülöp, Zoltán Tepavčević, Andreja Vogler, Heiko |
| contents | We consider the images of the initial algebra semantics of weighted tree automata over strong bimonoids (hence also over semirings). These images are subsets of the carrier set of the underlying strong bimonoid. We consider locally finite, weakly locally finite, and bi-locally finite strong bimonoids. We show that there exists a strong bimonoid which is weakly locally finite and not locally finite. We also show that if the ranked alphabet contains a binary symbol, then for any finitely generated strong bimonoid, weighted tree automata can generate, via their initial algebra semantics, all elements of the strong bimonoid. As a consequence of these results, for weakly locally finite strong bimonoids which are not locally finite, weighted tree automata can generate infinite images provided that the input ranked alphabet contains at least one binary symbol. This is in sharp contrast to the setting of weighted string automata, where each such image is known to be finite. As a further consequence, for any finitely generated semiring, there exists a weighted tree automaton which generates, via its run semantics, all elements of the semiring. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_20753 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The generating power of weighted tree automata with initial algebra semantics Droste, Manfred Fülöp, Zoltán Tepavčević, Andreja Vogler, Heiko Formal Languages and Automata Theory 68Q45, 03D05 (Primary), 68R99 (Secondary) We consider the images of the initial algebra semantics of weighted tree automata over strong bimonoids (hence also over semirings). These images are subsets of the carrier set of the underlying strong bimonoid. We consider locally finite, weakly locally finite, and bi-locally finite strong bimonoids. We show that there exists a strong bimonoid which is weakly locally finite and not locally finite. We also show that if the ranked alphabet contains a binary symbol, then for any finitely generated strong bimonoid, weighted tree automata can generate, via their initial algebra semantics, all elements of the strong bimonoid. As a consequence of these results, for weakly locally finite strong bimonoids which are not locally finite, weighted tree automata can generate infinite images provided that the input ranked alphabet contains at least one binary symbol. This is in sharp contrast to the setting of weighted string automata, where each such image is known to be finite. As a further consequence, for any finitely generated semiring, there exists a weighted tree automaton which generates, via its run semantics, all elements of the semiring. |
| title | The generating power of weighted tree automata with initial algebra semantics |
| topic | Formal Languages and Automata Theory 68Q45, 03D05 (Primary), 68R99 (Secondary) |
| url | https://arxiv.org/abs/2405.20753 |