Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Improved SAT models for NFA learning

Abstract : Grammatical inference is concerned with the study of algorithms for learning automata and grammars from words. We focus on learning Nondeterministic Finite Automaton of size k from samples of words. To this end, we formulate the problem as a SAT model. The generated SAT instances being enormous, we propose some model improvements, both in terms of the number of variables, the number of clauses, and clauses size. These improvements significantly reduce the instances, but at the cost of longer generation time. We thus try to balance instance size vs. generation and solving time. We also achieved some experimental comparisons and we analyzed our various model improvements.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03284571
Contributeur : Frédéric Lardeux <>
Soumis le : lundi 12 juillet 2021 - 16:25:50
Dernière modification le : mercredi 14 juillet 2021 - 03:35:20

Fichiers

ola2021.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-03284571, version 1
  • ARXIV : 2107.06672

Collections

Citation

Frédéric Lardeux, Eric Monfroy. Improved SAT models for NFA learning. International Conference in Optimization and Learning (OLA), Jun 2021, Catania, Italy. ⟨hal-03284571⟩

Partager

Métriques

Consultations de la notice

8

Téléchargements de fichiers

9