标题： 随机语言的恒等测试 显示英文标题

标题： Identity Testing for Stochastic Languages

摘要： 确定未知分布是否与已知参考分布匹配是分布分析中的一个基础问题。 虽然经典结果在有限域上的分布情况下建立了严格的框架，但计算语言学、生物信息学和程序分析中的实际应用需要在无限组合结构上进行测试，特别是字符串。 在本文中，我们开始了对随机语言身份测试的理论研究，将形式语言理论与现代分布属性测试相结合。 我们首先提出了一种多项式时间算法来验证有限状态机是否表示一个随机语言，然后证明有理随机语言可以近似任意概率分布。 基于这些表示，我们开发了一种基于截断的身份测试算法，其样本复杂度为$\widetilde{\Theta}\left( \frac{\sqrt{n}}{\varepsilon^2} + \frac{n}{\log n} \right)$，其中$n$是截断支持的大小。 我们的方法利用了有理随机语言中固有的指数衰减来限制截断误差，然后将经典有限域测试器应用于受限问题。 这项工作为无限离散分布建立了第一个身份测试框架，为概率形式方法和结构化数据的统计分析开辟了新的方向。 显示英文摘要

摘要： Determining whether an unknown distribution matches a known reference is a cornerstone problem in distributional analysis. While classical results establish a rigorous framework in the case of distributions over finite domains, real-world applications in computational linguistics, bioinformatics, and program analysis demand testing over infinite combinatorial structures, particularly strings. In this paper, we initiate the theoretical study of identity testing for stochastic languages, bridging formal language theory with modern distribution property testing. We first propose a polynomial-time algorithm to verify if a finite state machine represents a stochastic language, and then prove that rational stochastic languages can approximate an arbitrary probability distribution. Building on these representations, we develop a truncation-based identity testing algorithm that distinguishes between a known and an unknown distributions with sample complexity $\widetilde{\Theta}\left( \frac{\sqrt{n}}{\varepsilon^2} + \frac{n}{\log n} \right)$ where $n$ is the size of the truncated support. Our approach leverages the exponential decay inherent in rational stochastic languages to bound truncation error, then applies classical finite-domain testers to the restricted problem. This work establishes the first identity testing framework for infinite discrete distributions, opening new directions in probabilistic formal methods and statistical analysis of structured data.