Rational weighted tree languages with storage

We define the class of rational weighted tree languages with storage over complete, not necessarily commutative, semirings and we repeat its characterization by weighted regular tree grammars with storage. Moreover, we show an alternative proof of the fact that the class of rational weighted tree languages with storage is closed under the rational operations, i. e. , top-concatenation, scalar multiplication, sum, tree concatenation, and Kleene-star, where the latter two closure results require that the storage has a reset instruction.

Authors

• Frederic Dörband
• Zoltán Fülöp
• Heiko Vogler

Keywords

• Rational tree languages
• Grammars with storage
• Weighted tree automata