Angluin-Style Learning of~NFA

Abstract : We introduce NL*, a learning algorithm for inferring non-deterministic finite-state automata using membership and equivalence queries. More specifically, residual finite-state automata (RFSA) are learned similarly as in Angluin's popular L* algorithm, which, however, learns deterministic finite-state automata (DFA). Like in a DFA, the states of an RFSA represent residual languages. Unlike a DFA, an RFSA restricts to prime residual languages, which cannot be described as the union of other residual languages. In doing so, RFSA can be exponentially more succinct than DFA. They are, therefore, the preferable choice for many learning applications. The implementation of our algorithms is applied to a collection of examples and confirms the expected advantage of NL* over L*.
Type de document :
Communication dans un congrès
Boutilier, Craig. Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09), Jul 2009, Pasadena, CA, USA, United States. AAAI Press, pp.1004-1009, 2009
Liste complète des métadonnées

https://hal.inria.fr/hal-00772636
Contributeur : Stefan Haar <>
Soumis le : jeudi 10 janvier 2013 - 20:18:19
Dernière modification le : jeudi 11 janvier 2018 - 06:20:13

Identifiants

  • HAL Id : hal-00772636, version 1

Collections

Citation

Peter Habermehl, Carsten Kern, Martin Leucker, Benedikt Bollig. Angluin-Style Learning of~NFA. Boutilier, Craig. Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09), Jul 2009, Pasadena, CA, USA, United States. AAAI Press, pp.1004-1009, 2009. 〈hal-00772636〉

Partager

Métriques

Consultations de la notice

133