start
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
start [2018/11/14 11:42] – [New Features in ROLL v1.0] liyong | start [2020/12/16 15:03] (current) – [New Features in ROLL v1.0] 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 education | + | * Interactive mode for educational |
* 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:// | ||
---- | ---- | ||
- | Before going through other contents on this website, | + | Before going through other contents on this website, |
- | ==== Active Automata Learning Background Knowledge ==== | + | ===== Active Automata Learning Background Knowledge |
- | In the active automata learning setting proposed by Angluin [1], there are 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//. | ||
- | The teacher replies with a witness/ | + | The teacher replies with a witness/ |
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