证明了半自动机在统计查询模型下的学习难度，源于其状态转移结构。
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
- 通过随机游走建模状态转移，分析半自动机的不可学习性。
- 当字母表大小和输入长度为状态数的多项式时，学习困难性成立。
- 适用于对自动机理论和计算复杂性感兴趣的学者。
半自动机是一类广泛应用于自然语言处理、机器人学、计算生物学和数据挖掘的序列处理算法。本文首次在输入字串和初始状态的均匀分布下，建立了半自动机的统计查询学习难解性结果。当字母表大小和输入长度均为状态数的多项式时，该难解性成立。与确定有限自动机通常因所识别语言的困难性（如奇偶性）而难以学习不同，本结果仅由半自动机的内部状态转移结构导致。分析将区分两个半自动机的终态问题转化为研究群 $S_{N} imes S_{N}$ 上的随机游走行为。通过傅里叶分析和对称群表示论工具，获得紧的谱隙边界，证明在状态数的多项式步数后，不同半自动机几乎不相关，从而得出所需的难解性结论。
原文摘要 · Abstract (English)
Semiautomata form a rich class of sequence-processing algorithms with applications in natural language processing, robotics, computational biology, and data mining. We establish the first Statistical Query hardness result for semiautomata under the uniform distribution over input words and initial states. We show that Statistical Query hardness can be established when both the alphabet size and input length are polynomial in the number of states. Unlike the case of deterministic finite automata, where hardness typically arises through the hardness of the language they recognize (e.g., parity), our result is derived solely from the internal state-transition structure of semiautomata. Our analysis reduces the task of distinguishing the final states of two semiautomata to studying the behavior of a random walk on the group $S_{N} \times S_{N}$. By applying tools from Fourier analysis and the representation theory of the symmetric group, we obtain tight spectral gap bounds, demonstrating that after a polynomial number of steps in the number of states, distinct semiautomata become nearly uncorrelated, yielding the desired hardness result.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。