.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we present an L* -style algorithm for actively learning a bidirectional deterministic finite automaton (biDFA) in polynomial time using three types of oracles. We show how the W-method for the equivalence oracle can be adapted to our algorithm and present a novel heuristic for choosing the orientation of states. With this algorithm, one can identify automata for a subset of the linear languages that includes but is not limited to the regular languages. Since the equivalence oracle is an important part of the algorithm, we also discuss complexity bounds for different versions of the language equivalence problem for biDFAs. These results, together with our algorithm, also prove complexity bounds for the biDFA minimisation problem. Finally, we provide an implementation of the algorithm and experimentally show its performance with different approximation heuristics.
Keywords:
active learning
bidirectional deterministic finite automaton
equivalence oracle
W-method
minimisation problem
Journal
I
IF:
0
Papers:
22
Citations:
0
Organization
Cited Papers
No cited papers available