论文标题
计算线性船体：决定确定性？和明确的？对于字段上的加权自动机
Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields
论文作者
论文摘要
在一个场上加权自动机的（左）线性船体是拓扑不变的。如果自动机是最小的，则可以使用线性船体来确定自动机是否等于确定性。此外，线性船体还可以用于确定最小自动机是否等于明确的自动机。我们展示了如何计算线性船体，因此证明在数字字段上是否具有给定的自动机是可以决定的，等于确定性。在这种情况下，我们还能够计算等效的确定性自动机。我们还显示了明确情况下的类似可决定性和可计算性结果。我们的结果解决了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.
