Kleene and Büchi Theorems for Weighted Forest Languages over M-Monoids
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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
Originalsprache | Englisch |
---|---|
Aufsatznummer | 104765 |
Fachzeitschrift | Information and Computation |
Jahrgang | 281 |
Publikationsstatus | Veröffentlicht - Dez. 2021 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 85107062962 |
---|