EUVIMEDEUVIMED entdecken
Crossref

Learning DFAs from Positive Examples Only via Word Counting

Benjamin Bordais, Daniel Neider

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (17) · 14201-14208

DOI: 10.1609/aaai.v40i17.38433 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Benjamin Bordais und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Learning finite automata from positive examples has recently gained attention as a powerful approach for understanding, explaining, analyzing, and verifying black-box systems. The motivation for focusing solely on positive examples arises from the practical limitation that we can only observe what a system is capable of (positive examples) but not what it cannot do (negative examples). Unlike the classical problem of passive DFA learning with both positive and negative examples, which has been known to be NP-complete since the 1970s, the topic of learning DFAs exclusively from positive examples remains poorly understood. This paper introduces a novel perspective on this problem by leveraging the concept of counting the number of accepted words up to a carefully determined length. Our contributions are twofold. First, we prove that computing the minimal number of words up to this length accepted by DFAs of a given size that accept all positive examples is NP-complete, establishing that learning from positive examples alone is computationally demanding. Second, we propose a new learning algorithm with a better asymptotic runtime than the best-known bound for existing algorithms. While our experimental evaluation reveals that this algorithm under-performs state-of-the-art methods, it demonstrates significant potential as a preprocessing step to enhance existing approaches.

Zitieren

APA

Bordais, B., & Neider, D. (2026). Learning DFAs from Positive Examples Only via Word Counting. Proceedings of the AAAI Conference on Artificial Intelligence, 40(17), 14201-14208. https://doi.org/10.1609/aaai.v40i17.38433

Vancouver

Bordais B, Neider D. Learning DFAs from Positive Examples Only via Word Counting. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(17):14201-14208. doi:10.1609/aaai.v40i17.38433

BibTeX
@article{Bordais2026,
  author = {Bordais, Benjamin and Neider, Daniel},
  title = {Learning DFAs from Positive Examples Only via Word Counting},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {17},
  pages = {14201--14208},
  doi = {10.1609/aaai.v40i17.38433}
}
Kostenlos starten →