Angluin-Style Learning of NFA
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 1004-1008.
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
@inproceedings{ijcai2009p170,
title = {Angluin-Style Learning of NFA},
author = {Bollig, Benedikt and Habermehl, Peter and Kern, Carsten and Leucker, Martin},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {1004--1008},
year = {2009},
url = {https://ijcai.org/proceedings/2009/170},
}
TY - CPAPER TI - Angluin-Style Learning of NFA AU - Bollig, Benedikt AU - Habermehl, Peter AU - Kern, Carsten AU - Leucker, Martin T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 1004 EP - 1008 UR - https://ijcai.org/proceedings/2009/170 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
