Zoltán Fülöp ; Luisa Herrmann ; Heiko Vogler - Weighted Regular Tree Grammars with Storage

dmtcs:3664 - Discrete Mathematics & Theoretical Computer Science, July 3, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-26
Weighted Regular Tree Grammars with StorageArticle

Authors: Zoltán Fülöp ; Luisa Herrmann ; Heiko Vogler

    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.


    Volume: Vol. 20 no. 1
    Section: Automata, Logic and Semantics
    Published on: July 3, 2018
    Accepted on: June 22, 2018
    Submitted on: May 19, 2017
    Keywords: Computer Science - Formal Languages and Automata Theory,F.1.1,F.4.1,F.4.3

    Consultation statistics

    This page has been seen 573 times.
    This article's PDF has been downloaded 308 times.