双向非确定性补全的指数状态下界
An exponential state lower bound for two-way nondeterministic complementation
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件证明双向非确定性有限自动机不能以独立于字母表的多项式状态数进行补全。对于每个n≥4，构造一个有限字母表上的n状态自动机，其补全至少需要(1/2)2^{⌊(n-4)/127⌋}-1个状态。该结果属于自动机理论与计算复杂性领域，揭示了双向非确定性补全的状态复杂度下界。
- 证明双向非确定性有限自动机补全不能使用独立于字母表的多项式状态数。
- 对每个n≥4构造n状态自动机，其补全至少需要(1/2)2^{⌊(n-4)/127⌋}-1个状态。
- 给出指数状态下界的具体构造。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove that two-way nondeterministic finite automata cannot be complemented with a polynomial number of states independent of the alphabet. For each n ≥ 4 we construct an n-state automaton over a finite alphabet whose complement requires at least $`\tfrac12 2^{\lfloor(n-4)/127\rfloor}-1`$ states.
用户标记：未标记
固定编号：f40790c1fcf8e7ef
原文来源