Kleene and Büchi Theorems for Weighted Forest Languages over M-Monoids

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Aufsatznummer104765
FachzeitschriftInformation and Computation
Jahrgang281
PublikationsstatusVeröffentlicht - 2021
Peer-Review-StatusJa

Externe IDs

Scopus 85107062962

Schlagworte