一句话：给出有理数域上多重树自动机状态数最小化的多项式时间算法，并将其复杂度与多项式恒等测试相联系。
本文研究有理数域上多重树自动机的状态数最小化问题。作者提出一个在单位代价算术模型下多项式时间运行的最小化算法，并证明该最小化判定问题与多项式恒等测试（PIT）在对数空间意义下等价，因此若在标准图灵机上获得多项式界将意味着 PIT 复杂度突破。所提技术还改进多重词自动机的最小化，给出 NC 算法。最后研究最小一致性问题：给定带权词或树的有限样本，是否存在 n 个状态的一致自动机；作者证明该判定问题对词和固定字母秩树均对有理数存在理论（∃R）完全。
We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic. We also show that a polynomial bound in the standard Turing model would require a breakthrough in the complexity of polynomial identity testing by proving that the latter problem is logspace equivalent to the decision version of minimisation. The developed techniques also improve the state of the art in multiplicity word automata: we give an NC algorithm for minimising multiplicity word automata. Finally, we consider the minimal consistency problem: does there exist an automaton with $n$ states that is consistent with a given finite sample of weight-labelled words or trees? We show that this decision problem is complete for the existential theory of the rationals, both for words and for trees of a fixed alphabet rank.Comment: Paper to be published in Logical Methods in Computer Science. Minor editing changes from previous version
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{KieferMW15,
title = {Minimisation of Multiplicity Tree Automata},
author = {Stefan Kiefer and Ines Marusic and James Worrell},
journal = {Logical Methods in Computer Science},
volume = {Volume 13, Issue 1},
year = {2017},
doi = {10.23638/lmcs-13(1:16)2017}
}