一句话：证明多项式歧义有理加权自动机的确定化与无歧义化问题均在 PSPACE 中可判定。
加权自动机在有理数域上的确定化与无歧义化问题是：给定一个加权自动机，判定是否存在等价的确定性加权自动机，或等价的无歧义加权自动机。Bell 与 Smertnig 近期证明了该问题是可判定的，但没有给出复杂度界。本文研究多项式歧义加权自动机这一受限但自然的情形，证明确定化与无歧义化两个问题都可在 PSPACE 内判定，从而补上了此前缺失的复杂度上界。该结果为加权自动机的等价性与歧义性分析提供了新的复杂度视角。
We study the determinisation and unambiguisation problems of weighted automata over the field of rationals: Given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton? Recent results by Bell and Smertnig show that the problem is decidable, however they do not provide any complexity bounds. We show that both problems are in PSPACE for polynomially-ambiguous weighted automata.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{JeckerMP24,
title = {Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata},
author = {Ismaël Jecker and Filip Mazowiecki and David Purser},
booktitle = {LICS},
year = {2024},
doi = {10.1145/3661814.3662073}
}