Geodesic
Weighted Regular Tree Grammars with Storage
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1

Voir la notice de l'article provenant de la source Episciences

We introduce weighted regular tree grammars with storage as combination of (a) regular tree grammars with storage and (b) weighted tree automata over multioperator monoids. Each weighted regular tree grammar with storage generates a weighted tree language, which is a mapping from the set of trees to the multioperator monoid. We prove that, for multioperator monoids canonically associated to particular strong bi-monoids, the support of the generated weighted tree languages can be generated by (unweighted) regular tree grammars with storage. We characterize the class of all generated weighted tree languages by the composition of three basic concepts. Moreover, we prove results on the elimination of chain rules and of finite storage types, and we characterize weighted regular tree grammars with storage by a new weighted MSO-logic. 
@article{DMTCS_2018_20_1_a25,
     author = {F\"ul\"op, Zolt\'an and Herrmann, Luisa and Vogler, Heiko},
     title = {Weighted {Regular} {Tree} {Grammars} with {Storage}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     doi = {10.23638/DMTCS-20-1-26},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-26/}
}
TY  - JOUR
AU  - Fülöp, Zoltán
AU  - Herrmann, Luisa
AU  - Vogler, Heiko
TI  - Weighted Regular Tree Grammars with Storage
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-26/
DO  - 10.23638/DMTCS-20-1-26
LA  - en
ID  - DMTCS_2018_20_1_a25
ER  - 
%0 Journal Article
%A Fülöp, Zoltán
%A Herrmann, Luisa
%A Vogler, Heiko
%T Weighted Regular Tree Grammars with Storage
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-26/
%R 10.23638/DMTCS-20-1-26
%G en
%F DMTCS_2018_20_1_a25
Fülöp, Zoltán; Herrmann, Luisa; Vogler, Heiko. Weighted Regular Tree Grammars with Storage. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi: 10.23638/DMTCS-20-1-26

Cité par Sources :