Characterization of deterministically recognizable weighted tree languages over commutative semifields by finitely generated and cancellative scalar algebras
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909795906224128 |
|---|---|
| author | Fülöp, Zoltán Vogler, Heiko |
| author_facet | Fülöp, Zoltán Vogler, Heiko |
| contents | Due to the works of S. Bozapalidis and A. Alexandrakis, there is a well-known characterization of recognizable weighted tree languages over fields in terms of finite-dimensionality of syntactic vector spaces. Here we prove a characterization of bottom-up deterministically recognizable weighted tree languages over commutative semifields in terms of the requirement that the respective m-syntactic scalar algebras are finitely generated. The concept of scalar algebra is introduced in this paper; it is obtained from the concept of vector space by disregarding the addition of vectors. Moreover, we prove a minimization theorem for bottom-up-deterministic weighted tree automata and we construct the minimal automaton. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14914 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Characterization of deterministically recognizable weighted tree languages over commutative semifields by finitely generated and cancellative scalar algebras Fülöp, Zoltán Vogler, Heiko Formal Languages and Automata Theory Due to the works of S. Bozapalidis and A. Alexandrakis, there is a well-known characterization of recognizable weighted tree languages over fields in terms of finite-dimensionality of syntactic vector spaces. Here we prove a characterization of bottom-up deterministically recognizable weighted tree languages over commutative semifields in terms of the requirement that the respective m-syntactic scalar algebras are finitely generated. The concept of scalar algebra is introduced in this paper; it is obtained from the concept of vector space by disregarding the addition of vectors. Moreover, we prove a minimization theorem for bottom-up-deterministic weighted tree automata and we construct the minimal automaton. |
| title | Characterization of deterministically recognizable weighted tree languages over commutative semifields by finitely generated and cancellative scalar algebras |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2509.14914 |