Kleene and Büchi Theorems for Weighted Forest Languages over M-Monoids
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
Abstract
We consider forests as tuples of trees and introduce weighted forest automata (wfa) over M-monoids. A wfa acts on each individual tree in a forest like a weighted tree automaton over the same M-monoid. In order to combine the values of trees in forests, a wfa uses an associative multiplication operation that distributes over the addition of the M-monoid. We continue by introducing two semantics for wfa, an “initial algebra”-like semantic and a run-semantic, and prove that these semantics are equal for distributive M-monoids. We prove that our automaton model accepts finite products of recognizable weighted tree languages over M-monoids. Next, we introduce rational weighted forest expressions and forest M-expressions over M-monoids and show that the classes of languages generated by these formalisms coincide with recognizable weighted forest languages under certain conditions on the underlying M-monoid.
Details
Original language | English |
---|---|
Article number | 104765 |
Journal | Information and Computation |
Volume | 281 |
Publication status | Published - Dec 2021 |
Peer-reviewed | Yes |
External IDs
Scopus | 85107062962 |
---|