COMPLEXITY OF AUTOMATON IDENTIFICATION FROM GIVEN DATA
COMPLEXITY OF AUTOMATON IDENTIFICATION FROM GIVEN DATA
复制标题
DOI：
10.1016/s0019-9958(78)90562-4
复制
发表时间：
1978-01-01
影响因子：
--
通讯作者：
GOLD, EM
中科院分区：
文献类型：
--
作者：
GOLD, EM
尽管有限自动机的极限识别可能在多项式时间内作为d的大小的函数，但是否存在与有限集数据一致的状态自动机的问题被证明是benp完备的。给出了一个自动机可以实现的充分必要条件，该自动机的状态可以通过给定的输入字符串集合从初始状态到达。虽然这个问题也是sonp完备的，但这些条件建议采用启发式方法。即使这个问题的解决方案是可用的，也表明找到最小的set不一定会给出最小的可能let。
The question of whether there is an automaton withnstates which agrees with a finite setDof data is shown to beNP-complete, although identification-in-the-limit of finite automata is possible in polynomial time as a function of the size ofD. Necessary and sufficient conditions are given forDto be realizable by an automaton whose states are reachable from the initial state by a given setTof input strings. Although this question is alsoNP-complete, these conditions suggest heuristic approaches. Even if a solution to this problem were available, it is shown that finding a minimal setTdoes not necessarily give the smallest possibleT.