Approximated Determinisation of Weighted Tree Automata
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-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 language | English |
---|---|
Title of host publication | Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings |
Editors | Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron |
Pages | 255-266 |
Number of pages | 12 |
ISBN (electronic) | 978-3-030-68195-1 |
Publication status | Published - 2021 |
Peer-reviewed | Yes |
External IDs
Scopus | 85104377868 |
---|
Keywords
ASJC Scopus subject areas
Keywords
- approximated determinization, approximation, tree automata, twinning property, weighted tree automata, Approximation, Twinning property, Weighted automata, Tree automata, Approximated determinisation, determinization