Efficient enumeration of weighted tree languages over the tropical semiring
作者：
Highlights：
• The algorithm does not “only” compute the N best runs, but indeed the N best-scoring trees according to the input automaton.
• We provide detailed arguments for the correctness and the running time of the algorithm (which had to be left out in the proceedings version).
• The algorithm runs in polynomial time and is not much less efficient than the recent best-runs algorithm by Büchse et al.
摘要
•The algorithm does not “only” compute the N best runs, but indeed the N best-scoring trees according to the input automaton.•We provide detailed arguments for the correctness and the running time of the algorithm (which had to be left out in the proceedings version).•The algorithm runs in polynomial time and is not much less efficient than the recent best-runs algorithm by Büchse et al.
论文关键词：Weighted tree automaton,N-best analysis,Tropical semiring
论文评审过程：Received 29 June 2015, Revised 10 February 2017, Accepted 20 March 2017, Available online 6 April 2017, Version of Record 6 June 2019.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.03.006
