User Tools

Site Tools


start

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
start [2018/11/16 15:38]
liyong [New Features in ROLL v1.0]
start [2020/12/16 15:03] (current)
liyong [New Features in ROLL v1.0]
Line 16: Line 16:
      * the algorithm in [4] learns a Büchi automaton by combining L<​sup>​*</​sup>​ algorithm [1] and results in [2],      * the algorithm in [4] learns a Büchi automaton by combining L<​sup>​*</​sup>​ algorithm [1] and results in [2],
      * 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://​www.brics.dk/​automaton/​|dk.brics.automaton]] package. We use [[http://​www.languageinclusion.org/​doku.php?​id=tools|RABIT]] tool to check the equivalence of The ROLL library is implemented in JAVA. Its DFA operations are delegated to the [[http://​www.brics.dk/​automaton/​|dk.brics.automaton]] package. We use [[http://​www.languageinclusion.org/​doku.php?​id=tools|RABIT]] tool to check the equivalence of
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://​iscasmc.ios.ac.cn/​roll/​jupyter|Jupyter notebook for ROLL]] (requires ​**websockets** to run correctly).+  * [[https://​iscasmc.ios.ac.cn/​roll/​jupyter|Jupyter notebook for ROLL]] (You can **play with ROLL online** !!!).
   * 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 ​[9] of [8]).
   * [[http://​adl.github.io/​hoaf/​|Hanoi omega-automata format]]. ​   * [[http://​adl.github.io/​hoaf/​|Hanoi omega-automata format]]. ​
  
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 are a //​teacher//, ​which knows the target language //L//, and a //​learner//,​ whose task is to learn from the teacher the target language, represented by an automaton.+In the active automata learning setting proposed by Angluin [1], there is a //​teacher//, ​who knows the target language //L//, and a //​learner//,​ whose task is to learn from the teacher the target language, represented by an automaton.
 The learner interacts with the teacher by means of two kinds of queries: //​membership queries// and //​equivalence queries//. The learner interacts with the teacher by means of two kinds of queries: //​membership queries// and //​equivalence 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."​ In TACAS. Springer-Verlag Berlin, Heidelberg, 2005:​271-286. [8] Radu Grosu, Scott A. Smolka. "Monte carlo model checking."​ In TACAS. Springer-Verlag Berlin, Heidelberg, 2005:​271-286.
  
 +[9] Yong Li, Andrea Turrini, Xuechao Sun and Lijun Zhang. "​Proving Non-inclusion of Büchi Automata Based on Monte Carlo Sampling."​ In ATVA. Springer, 2020: 467-483.
  
-[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."​ To appear. {{ :LDBA.pdf |preprint}} (Added an algorithm to transform an FDFA to a limit-deterministic Büchi automaton)+ 
 +[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."​ To appear ​in I&C. {{ :iandc.pdf |preprint}} (Added an algorithm to transform an FDFA to a limit-deterministic Büchi automaton)
  
  
  
start.1542353923.txt.gz · Last modified: 2018/11/16 15:38 by liyong