从单个字符串的前缀学习最小有限状态机是计算上难解的。
Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete
- 研究单个二进制串所有前缀的最小确定有限自动机学习问题。
- 证明该问题在近似和决策层面均属NP难，即使输入仅来自一个字符串。
- 结果对莫尔机和米利机也成立，适用于形式化验证与系统逆向工程。
已知根据正负样例计算最小一致的确定性有限自动机是NP难的。以往工作识别了输入样本满足某些条件时问题可解或仍难。本文研究输入样本为前缀闭集的情形，这等价于求解与运行观测一致的最小莫尔机。我们证明：当样本集为二进制字符串的所有前缀时，该问题难以近似；进一步，即使样本仅为单一二进制字符串的前缀，其判定问题仍为NP难。该结论还适用于相应的米利机问题。
原文摘要 · Abstract (English)
It is well known that computing a minimum deterministic finite automaton consistent with a given set of positive and negative examples is NP-hard. Previous work has identified conditions on the input sample under which the problem becomes tractable or remains hard. In this paper, we study the computational complexity of the case where the input sample is prefix-closed. This formulation is equivalent to computing a minimum Moore machine consistent with observations along its runs. We show that the problem is NP-hard to approximate when the sample set consists of all prefixes of binary strings. Furthermore, we show that the problem remains NP-hard as a decision problem even when the sample set consists of the prefixes of a single binary string. Our argument also extends to the corresponding problem for Mealy machines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。