一句话：研究加权自动机间的 Big-O 关系，证明其一般不可判定，并给出多个可判定子类的复杂度。
本文研究两个加权自动机间的 Big-O 问题：判定第一个自动机每个有限词的权重是否不超过第二个权重的某个常数倍。作者证明该问题一般不可判定，即使实例化为标签马尔可夫链仍不可判定；即使已知 Big-O 关系成立，寻找或逼近常数也不可判定。正面结果：无歧义自动机多项式时间可解，单字母表无标签加权自动机 coNP 完全，在 Schanuel 猜想下语言有界或有限歧义时可判定。在标签马尔可夫链上，该问题重述为比率全变差距离，并联系 ε-差分隐私，最优常数为 exp(ε)。
Given two weighted automata, we consider the problem of whether one is big-O of the other, i.e., if the weight of every finite word in the first is not greater than some constant multiple of the weight in the second. We show that the problem is undecidable, even for the instantiation of weighted automata as labelled Markov chains. Moreover, even when it is known that one weighted automaton is big-O of another, the problem of finding or approximating the associated constant is also undecidable. Our positive results show that the big-O problem is polynomial-time solvable for unambiguous automata, coNP-complete for unlabelled weighted automata (i.e., when the alphabet is a single character) and decidable, subject to Schanuel's conjecture, when the language is bounded (i.e., a subset of $w_1^*\dots w_m^*$ for some finite words $w_1,\dots,w_m$) or when the automaton has finite ambiguity. On labelled Markov chains, the problem can be restated as a ratio total variation distance, which, instead of finding the maximum difference between the probabilities of any two events, finds the maximum ratio between the probabilities of any two events. The problem is related to $\varepsilon$-differential privacy, for which the optimal constant of the big-O notation is exactly $\exp(\varepsilon)$.
@article{paperbot1714,
title = {The Big-O Problem},
author = {Dmitry Chistikov and Stefan Kiefer and Andrzej S. Murawski and David Purser},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 1},
year = {2022},
doi = {10.46298/lmcs-18(1:40)2022}
}