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

Research output: Contribution to journalResearch articleContributedpeer-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 languageEnglish
Article number104765
JournalInformation and Computation
Volume281
Publication statusPublished - Dec 2021
Peer-reviewedYes

External IDs

Scopus 85107062962

Keywords