一句话：证明 monitor counter 自动机与嵌套加权自动机等价，并刻画其在概率语义下的可判定性与复杂度。
定量性质常由带 monitor counter 的自动机和嵌套加权自动机描述；这两类框架对一大类定量函数具有等价表达力。本文首次在概率语义下研究此类定量自动机，即转移按概率选择，并考察接受、空性、普遍性等概率问题。作者证明，经典语义下不可判定的空性与普遍性在概率语义下变得可判定，并给出所考虑概率问题的完整可判定性图景，以及几乎完整的计算复杂度分类。
Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor counters and nested weighted automata are equivalent. We study for the first time such quantitative automata under probabilistic semantics. We show that several problems that are undecidable for the classical questions of emptiness and universality become decidable under the probabilistic semantics. We present a complete picture of decidability for such automata, and even an almost-complete picture of computational complexity, for the probabilistic questions we consider.
@article{paperbot769,
title = {Quantitative Automata under Probabilistic Semantics},
author = {Krishnendu Chatterjee and Thomas A. Henzinger and Jan Otop},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 3},
year = {2019},
doi = {10.23638/lmcs-15(3:16)2019}
}