一句话：给出计算域上加权自动机线性包的算法，判定其是否等价于确定或无歧义自动机，并解决2006年公开问题。
论文研究域上加权自动机的确定性与无歧义性判定问题。若自动机最小，其左线性包这一拓扑不变量可用于判断它是否等价于确定自动机或无歧义自动机；但此前不知道如何计算线性包。作者给出线性包的计算方法，从而证明在数域上可判定给定自动机是否等价于确定自动机，并能构造等价的确定自动机。无歧义情形也得到类似的判定与可计算性结果。该工作解决了 Lombardy 与 Sakarovitch 在2006年综述中提出的问题。
The (left) linear hull of a weighted automaton over a field is a topological invariant. If the automaton is minimal, the linear hull can be used to determine whether or not the automaton is equivalent to a deterministic one. Furthermore, the linear hull can also be used to determine whether the minimal automaton is equivalent to an unambiguous one. We show how to compute the linear hull, and thus prove that it is decidable whether or not a given automaton over a number field is equivalent to a deterministic one. In this case we are also able to compute an equivalent deterministic automaton. We also show the analogous decidability and computability result for the unambiguous case. Our results resolve a problem posed in a 2006 survey by Lombardy and Sakarovitch.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{BellS23,
title = {Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields},
author = {Jason P. Bell and Daniel Smertnig},
booktitle = {LICS},
year = {2023},
doi = {10.1109/lics56636.2023.10175691}
}