.png){kind=icon}
返回
An Active Learning Algorithm for Bidirectional Deterministic Finite Automata
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-02602-6_8.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本文提出了一种L*风格算法，利用三种类型的预言机（oracle）在多项式时间内主动学习双向确定性有限自动机（biDFA）。我们展示了如何将W方法应用于等价预言机，并提出了一种新颖的状态方向选择启发式方法。通过该算法，可以识别一类线性语言的自动机，该类语言包含但不限于正则语言。由于等价预言机是算法的重要部分，我们还讨论了biDFA不同语言等价问题的复杂度界。这些结果与我们的算法共同证明了biDFA最小化问题的复杂度界。最后，我们提供了算法的实现，并通过实验展示了其在不同近似启发式下的性能。
Keyword:
active learning
bidirectional deterministic finite automaton
equivalence oracle
W-method
minimisation problem
期刊
I
IF:
0
论文数:
22
被引数:
0
机构
引用论文
暂无论文信息