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 revisionPrevious revision
Next revision
Previous revision
start [2019/01/08 11:07] – [Active Automata Learning Background Knowledge] liyongstart [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<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 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.txt · Last modified: 2020/12/16 15:03 by liyong