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

Optimized models and symmetry breaking for the NFA inference problem

Abstract : Grammatical inference is concerned with the study of algorithms for learning automata and grammars from words. We propose some models for learning Nondeterministic Finite Automaton (NFA) of size k from samples of words of the language and words not belonging to the language we want to describe. To this end, we formulate the problem as a SAT model trying to reduce the size of generated SAT instances. We propose new models to generate even smaller SAT instances. We also suggest some techniques for breaking some symmetries, hence reducing the search space, and consequently, speeding-up solving. We also achieved some experimental comparisons and we analyze our various model improvements and over-constraint propositions. Compared to [1], our models are easier and faster to solve. Compare to the parallel solver of [2], we find some new bounds for some instances for which the minimal size of NFA is not known yet.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03613517
Contributeur : Frédéric lardeux Connectez-vous pour contacter le contributeur
Soumis le : vendredi 18 mars 2022 - 15:11:03
Dernière modification le : lundi 14 novembre 2022 - 02:42:07
Archivage à long terme le : : dimanche 19 juin 2022 - 19:04:59

Fichier

ICTAI-2021.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Frédéric Lardeux, Eric Monfroy. Optimized models and symmetry breaking for the NFA inference problem. 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2021, Washington, France. pp.396-403, ⟨10.1109/ICTAI52525.2021.00065⟩. ⟨hal-03613517⟩

Partager

Métriques

Consultations de la notice

5

Téléchargements de fichiers

19