start
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
start [2019/01/08 11:07] – [Active Automata Learning Background Knowledge] liyong | start [2020/12/16 15:00] – [Active Automata Learning Background Knowledge] liyong | ||
---|---|---|---|
Line 16: | Line 16: | ||
* the algorithm in [4] learns a Büchi automaton by combining L< | * the algorithm in [4] learns a Büchi automaton by combining L< | ||
* the algorithm in [6] learns the Büchi automata via learning three canonical FDFAs. | * the algorithm in [6] learns the Büchi automata via learning three canonical FDFAs. | ||
- | * the algorithm in [9] learns the limit-deterministic Büchi automata via learning three canonical FDFAs. | + | * the algorithm in [10] learns the limit-deterministic Büchi automata via learning three canonical FDFAs. |
| | ||
The ROLL library is implemented in JAVA. Its DFA operations are delegated to the [[http:// | The ROLL library is implemented in JAVA. Its DFA operations are delegated to the [[http:// | ||
Line 25: | Line 25: | ||
Compared to its previous version, it now supports new features such as: | Compared to its previous version, it now supports new features such as: | ||
* Learning algorithm for limit-deterministic Büchi automata. | * Learning algorithm for limit-deterministic Büchi automata. | ||
- | * [[https:// | + | * [[https:// |
* Interactive mode for educational purpose. | * Interactive mode for educational purpose. | ||
* Büchi automata complementation based on learning [7]. | * Büchi automata complementation based on learning [7]. | ||
* Büchi automata inclusion testing based on word sampling and learning. | * Büchi automata inclusion testing based on word sampling and learning. | ||
- | * PAC-learning for Büchi automata based on Monte-Carlo word sampling (our improved version of [8]). | + | * PAC-learning for Büchi automata based on Monte-Carlo word sampling (our improved version |
* [[http:// | * [[http:// | ||
Line 36: | Line 36: | ||
===== Active Automata Learning Background Knowledge ===== | ===== Active Automata Learning Background Knowledge ===== | ||
- | In the active automata learning setting proposed by Angluin [1], there is a // | + | In the active automata learning setting proposed by Angluin [1], there is a // |
The learner interacts with the teacher by means of two kinds of queries: // | The learner interacts with the teacher by means of two kinds of queries: // | ||
A membership query //MQ[w]// asks whether a string //w// belongs to //L// while an equivalence query //EQ[A]// asks whether the hypothesis automaton //A// recognizes //L//. | A membership query //MQ[w]// asks whether a string //w// belongs to //L// while an equivalence query //EQ[A]// asks whether the hypothesis automaton //A// recognizes //L//. | ||
Line 61: | Line 61: | ||
[8] Radu Grosu, Scott A. Smolka. "Monte carlo model checking." | [8] Radu Grosu, Scott A. Smolka. "Monte carlo model checking." | ||
+ | [9] Yong Li, Andrea Turrini, Xuechao Sun and Lijun Zhang. " | ||
- | [9] Yong Li, Yu-Fang Chen, Lijun Zhang, and Depeng Liu. "A Novel Learning Algorithm for Büchi Automata based on Family of DFAs and Classification Trees." | + | |
+ | [10] Yong Li, Yu-Fang Chen, Lijun Zhang, and Depeng Liu. "A Novel Learning Algorithm for Büchi Automata based on Family of DFAs and Classification Trees." | ||
start.txt · Last modified: 2020/12/16 15:03 by liyong