Approximated Determinisation of Weighted Tree Automata

From International Center for Computational Logic

Toggle side column

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
  • 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: DeciGUTQuantLA
  • 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}
}