对无限字母表上的寄存式自动机和转换器的单次使用限制
内容提要
本文研究了一元量子有限自动机的两种模型：一次测量和多次测量。证明了一次测量模型能够解决自由群的词问题，并探讨了多次测量自动机的语言接受性质。此外，介绍了新的构造技术，使得某些语言可以被量子有限自动机接受，并指出一维量子有限自动机的能力弱于正则语言。
延伸解读
一次测量模型与自由群词问题的关联
文章证明一次测量量子有限自动机在有界误差下可解决自由群上的词问题。自由群词问题是群论中的经典判定问题，通常需要线性时间算法。该结果表明，即使是一元量子有限自动机，在限制测量次数后，仍具有解决特定代数问题的计算能力，这为量子自动机与形式语言理论的交叉提供了新视角。
多次测量模型的语言封闭性质与必要条件
对于多次测量量子有限自动机，文章探讨了其接受语言的封闭性质，并提出了一个新的必要条件。封闭性质有助于理解这类自动机可接受语言类的结构，而必要条件则为判断一个语言是否可被该模型接受提供了理论工具。这些结果深化了对多次测量模型计算能力的认识。
新构造技术扩展可接受语言范围
文章引入新的构造技术，使得某些分段可测试语言可被多次测量量子有限自动机接受。分段可测试语言是一类具有局部测试特性的形式语言，这一构造表明多次测量模型的能力可覆盖部分非正则语言，从而扩展了量子有限自动机的语言接受范围。
一维量子有限自动机的能力局限
文章指出一维量子有限自动机的接受能力弱于正则语言。这意味着存在正则语言无法被一维量子有限自动机识别，揭示了该模型在计算能力上的固有局限。这一结论与经典有限自动机形成对比，有助于界定量子有限自动机在形式语言层级中的位置。
Q&A
什么是一元量子有限自动机的模型？
一元量子有限自动机有两种模型：一次测量模型和多次测量模型。
一次测量模型能解决什么问题？
一次测量模型能够解决自由群的词问题，并接受有界误差。
多次测量自动机的语言接受性质是什么？
多次测量自动机的语言接受性质被探讨，并提出了新的必要条件。
新的构造技术对量子有限自动机有什么影响？
新的构造技术使得某些分段可测试语言可以被多次测量量子有限自动机接受。
一维量子有限自动机的能力如何？
一维量子有限自动机的能力弱于正则语言。
一次测量和多次测量自动机有什么区别？
一次测量自动机只进行一次测量，而多次测量自动机可以进行多次测量，影响其语言接受性质。
