Home

Regular Omega Language Learning (ROLL)

ROLL is a Library of learning algorithms for ω-regular languages. It consists of all full ω-regular learning algorithms available in the literature, namely

• the learning algorithm for FDFAs
  • the algorithm in [5] learns three canonical FDFAs using observation tables, which is based on results in [3],
  • the algorithm in [6] learns three canonical FDFAs using classification trees;
• and the learning algorithm for Büchi automata
  • the algorithm in [4] learns a Büchi automaton by combining L^* algorithm [1] and results in [2],
  • the algorithm in [6] learns the Büchi automata via learning three canonical FDFAs.

The ROLL library is implemented in JAVA. Its DFA operations are delegated to the dk.brics.automaton package. We use RABIT tool to check the equivalence of two Büchi automata. For more information about ROLL, please visit our tool website. We provide a simple guide to set up ROLL in Eclipse on this wiki.

---

[1] Dana Angluin. "Learning regular sets from queries and counterexamples." Information and computation 75.2 (1987): 87-106.

[2] Hugues Calbrix, Maurice Nivat, and Andreas Podelski. "Ultimately periodic words of rational ω-languages." In MFPS. Springer Berlin Heidelberg, 1993: 554-566.

[3] Oded Maler and Ludwig Staiger. "On syntactic congruences for ω-languages." In STACS. Springer Berlin Heidelberg, 1993: 586-594.

[4] Azadeh Farzan, Yu-Fang Chen, Edmund M. Clarke, Yih-Kuen Tsay, Bow-Yaw Wang. "Extending automated compositional verification to the full class of omega-regular languages." In TACAS. Springer Berlin Heidelberg, 2008: 2-17.

[5] Dana Angluin, and Dana Fisman. "Learning regular omega languages." In ALT. Springer International Publishing, 2014: 125-139.

[6] 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." In TACAS. Springer Berlin Heidelberg, 2017: 208-226.