Approximated Determinisation of Weighted Tree Automata

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

Abstract

We introduce the notion of t-approximated determinisation and the t-twinning property of weighted tree automata (WTA) over the tropical semiring. We provide an algorithm that accomplishes t-approximated determinisation of an input automaton A, whenever it terminates. Moreover, we prove that the t-twinning property of A is a sufficient condition for the termination of our algorithm. Ultimately, we show decidability of the t-twinning property for WTA.

Details

OriginalspracheEnglisch
TitelLanguage and Automata Theory and Applications
Seiten255-266
Seitenumfang12
ISBN (elektronisch)978-3-030-68195-1
PublikationsstatusVeröffentlicht - 2021
Peer-Review-StatusJa

Externe IDs

Scopus 85104377868

Schlagworte

Schlagwörter

  • weighted tree automata, twinning property, approximation, approximated determinization, tree automata, determinization