ML Anthology

Angluin-Style Learning of NFA

Benedikt Bollig, Peter Habermehl, Carsten Kern, Martin Leucker
IJCAI 2009 pp. 1004-1009
/ijcai/2009/bollig2009ijcai-angluin/

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 algorithm is applied to a collection of examples and confirms the expected advantage of NL* over L*. Benedikt Bollig, Peter Habermehl, Carsten Kern, Martin Leucker

PDF Semantic Scholar

Cite

Text

Bollig et al. "Angluin-Style Learning of NFA." International Joint Conference on Artificial Intelligence, 2009.

Markdown

[Bollig et al. "Angluin-Style Learning of NFA." International Joint Conference on Artificial Intelligence, 2009.](https://mlanthology.org/ijcai/2009/bollig2009ijcai-angluin/)

BibTeX

@inproceedings{bollig2009ijcai-angluin,
  title     = {{Angluin-Style Learning of NFA}},
  author    = {Bollig, Benedikt and Habermehl, Peter and Kern, Carsten and Leucker, Martin},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2009},
  pages     = {1004-1009},
  url       = {https://mlanthology.org/ijcai/2009/bollig2009ijcai-angluin/}
}