一句话：将代数幂级数的零性、有限支撑和系数计算归约到算术电路，改进了复杂度上界，并给出上下文无关文法重数等价等推论。
论文研究多个交换变量上的代数幂级数（由多项式方程组指定，与带权上下文无关文法密切相关）的三个计算问题：判定级数是否恒为零、是否除有限多项外系数全为零，以及计算指定单项式系数。作者将这些问题的复杂度联系到算术电路上的经典问题，证明三者均属于计数层级。主要结果把代数级数零性判定的最好已知上界从 PSPACE 改进到计数层级，归约到算术电路给定多项式的次数计算。作为推论，论文给出有界语言上上下文无关文法重数等价、NFA 到无歧义 CFG 的语言包含、非确定性 CFG 到无歧义有限自动机的语言包含等问题的新的复杂度上界。
In this paper we obtain complexity bounds for computational problems on algebraic power series over several commuting variables. The power series are specified by systems of polynomial equations: a formalism closely related to weighted context-free grammars. We focus on three problems—decide whether a given algebraic series is identically zero, determine whether all but finitely many coefficients are zero, and compute the coefficient of a specific monomial. We relate these questions to well-known computational problems on arithmetic circuits and thereby show that all three problems lie in the counting hierarchy. Our main result improves the best known complexity bound on deciding zeroness of an algebraic series. This problem is known to lie in PSPACE by reduction to the decision problem for the existential fragment of the theory of real closed fields. Here we show that the problem lies in the counting hierarchy by reduction to the problem of computing the degree of a polynomial given by an arithmetic circuit. As a corollary we obtain new complexity bounds on multiplicity equivalence of context-free grammars restricted to a bounded language, language inclusion of a non-deterministic finite automaton in an unambiguous context-free grammar, and language inclusion of a non-deterministic context-free grammar in an unambiguous finite automaton.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{abs-2304-14145,
title = {Multiplicity Problems on Algebraic Series and Context-Free Grammars},
author = {Nikhil Balaji and Lorenzo Clemente and Klara Nosan and Mahsa Shirmohammadi and James Worrell},
booktitle = {LICS},
year = {2023},
doi = {10.1109/lics56636.2023.10175707}
}