Approximated Determinisation of Weighted Tree Automata

Frederic DörbandFrederic Dörband, Thomas FellerThomas Feller, Kevin StierKevin Stier

Frederic Dörband, Thomas Feller, Kevin Stier
Approximated Determinisation of Weighted Tree Automata
In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron, eds., Language and Automata Theory and Applications. LATA 2021., volume 12638 of Lecture Notes in Computer Science, 255-266, February 2021. Springer

Details
Bibtex

KurzfassungAbstract
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.
Projekt:Project: DeciGUT, QuantLA
Forschungsgruppe:Research Group: Computational LogicComputational Logic

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-030-68195-1_20.

@inproceedings{DFS2021,
  author    = {Frederic D{\"{o}}rband and Thomas Feller and Kevin Stier},
  title     = {Approximated Determinisation of Weighted Tree Automata},
  editor    = {Alberto Leporati and Carlos Mart{\'{\i}}n-Vide and Dana Shapira
               and Claudio Zandron},
  booktitle = {Language and Automata Theory and Applications. {LATA} 2021.},
  series    = {Lecture Notes in Computer Science},
  volume    = {12638},
  publisher = {Springer},
  year      = {2021},
  month     = {February},
  pages     = {255-266},
  doi       = {10.1007/978-3-030-68195-1_20}
}