Approximated Determinisation of Weighted Tree Automata

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

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

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings
EditorsAlberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron
Pages255-266
Number of pages12
ISBN (electronic)978-3-030-68195-1
Publication statusPublished - 2021
Peer-reviewedYes

External IDs

Scopus 85104377868

Keywords

Keywords

  • approximated determinization, approximation, tree automata, twinning property, weighted tree automata, Approximation, Twinning property, Weighted automata, Tree automata, Approximated determinisation, determinization