Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2409.08727 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912026647855104 |
|---|---|
| author | Droste, Manfred Vogler, Heiko |
| author_facet | Droste, Manfred Vogler, Heiko |
| contents | We consider weighted automata over words and over trees where the weight algebras are strong bimonoids, i.e., semirings which may lack distributivity. It is well known that, for each such weighted automaton, its run semantics and its initial algebra semantics can be different, due to the presence of nondeterminism and the absence of distributivity. Here we investigate the question under which conditions on the strong bimonoid the support of the run semantics equals the support of the initial algebra semantics. We prove a characterization of this equality in terms of strongly zero-sum-free strong bimonoids (for weighted automata over words) and in terms of bi-strongly zero-sum-free strong bimonoids (for weighted automata over trees). We also consider shortly the images of the two semantics functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08727 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Run supports and initial algebra supports of weighted automata Droste, Manfred Vogler, Heiko Formal Languages and Automata Theory 68Q45 (Primary) 03D05, 03D15 (Secondary) F.4.3 We consider weighted automata over words and over trees where the weight algebras are strong bimonoids, i.e., semirings which may lack distributivity. It is well known that, for each such weighted automaton, its run semantics and its initial algebra semantics can be different, due to the presence of nondeterminism and the absence of distributivity. Here we investigate the question under which conditions on the strong bimonoid the support of the run semantics equals the support of the initial algebra semantics. We prove a characterization of this equality in terms of strongly zero-sum-free strong bimonoids (for weighted automata over words) and in terms of bi-strongly zero-sum-free strong bimonoids (for weighted automata over trees). We also consider shortly the images of the two semantics functions. |
| title | Run supports and initial algebra supports of weighted automata |
| topic | Formal Languages and Automata Theory 68Q45 (Primary) 03D05, 03D15 (Secondary) F.4.3 |
| url | https://arxiv.org/abs/2409.08727 |