一句话：提出自动机宽度度量以量化非确定性，并研究其确定化与计算复杂度。
论文引入“宽度”（width）这一度量，用于刻画非确定性自动机中非确定性的程度。宽度推广了 good-for-games（GFG）自动机：GFG 恰为宽度 1 的 NFA，即在任意被接受输入上可在线构造接受运行。作者基于宽度给出一种 NFA 的增量确定化构造，其效率可优于完整幂集确定化，且可推广到无限字，尤其适用于 coBüchi 自动机。对 coBüchi 自动机，该过程可构造确定自动机或 GFG 自动机，并在后者情形更高效。作者证明判定 coBüchi 自动机是否可经剪枝确定化是 NP-complete；在有限字或无限字上，计算自动机宽度是 EXPTIME-complete，由此推出 NFA 上多石子模拟博弈也是 EXPTIME-complete。
We introduce a measure called width, quantifying the amount of nondeterminism in automata. Width generalises the notion of good-for-games (GFG) automata, that correspond to NFAs of width 1, and where an accepting run can be built on-the-fly on any accepted input. We describe an incremental determinisation construction on NFAs, which can be more efficient than the full powerset determinisation, depending on the width of the input NFA. This construction can be generalised to infinite words, and is particularly well-suited to coB\"uchi automata. For coB\"uchi automata, this procedure can be used to compute either a deterministic automaton or a GFG one, and it is algorithmically more efficient in the last case. We show this fact by proving that checking whether a coB\"uchi automaton is determinisable by pruning is NP-complete. On finite or infinite words, we show that computing the width of an automaton is EXPTIME-complete. This implies EXPTIME-completeness for multipebble simulation games on NFAs.