Insights to {A}ngluin's Learning

TitleInsights to {A}ngluin's Learning
Publication TypeConference Paper
Year of Publication2003
AuthorsBerg, T, Jonsson, B, Leucker, M, Saksena, M
Conference NameProceedings of the International Workshop on Software Verification and Validation (SVV 2003)
SeriesElectronic Notes in Theoretical Computer Science
Volume118
Abstract

Among other domains, learning finite-state machines is important for obtaining a model of a system under development, so that powerful formal methods such as model checking can be applied. A prominent algorithm for learning such devices was developed by Angluin. We have implemented this algorithm in a straightforward way to gain further insights to practical applicability. Furthermore, we have analyzed its performance on randomly generated as well as real-world examples. Our experiments focus on the impact of the alphabet size and the number of states on the needed number of membership queries. Additionally, we have implemented and analyzed an optimized version for learning prefix-closed regular languages. Memory consumption is one major obstacle when we attempted to learn large examples. We see that prefix-closed languages are relatively hard to learn compared to arbitrary regular languages. The optimization, however, shows positive results.

URLhttp://www.sciencedirect.com/science?_ob=MImg&_imagekey=B75H1-4FFN49V-18-1&_cdi=13109&_user=616147&_orig=browse&_coverDate=02%2F01%2F2005&_sk=998819999&view=c&wchp=dGLbVlz-zSkzV&md5=1cd6a1fcf1599d96b97a2e45a181c0e5&ie=/sdarticle.pdf
Bibtex: 
@inproceedings {BergJLS03,
	title = {Insights to {A}ngluin{\textquoteright}s Learning},
	booktitle = {Proceedings of the International Workshop on Software Verification and Validation (SVV 2003)},
	series = {Electronic Notes in Theoretical Computer Science},
	volume = {118},
	year = {2003},
	pages = {3{\textendash}18},
	abstract = {Among other domains, learning finite-state machines is important for obtaining a model of a system under development, so that powerful formal methods such as model checking can be applied. A prominent algorithm for learning such devices was developed by Angluin. We have implemented this algorithm in a straightforward way to gain further insights to practical applicability. Furthermore, we have analyzed its performance on randomly generated as well as real-world examples. Our experiments focus on the impact of the alphabet size and the number of states on the needed number of membership queries. Additionally, we have implemented and analyzed an optimized version for learning prefix-closed regular languages. Memory consumption is one major obstacle when we attempted to learn large examples. We see that prefix-closed languages are relatively hard to learn compared to arbitrary regular languages. The optimization, however, shows positive results.},
	url = {http://www.sciencedirect.com/science?_ob=MImg\&_imagekey=B75H1-4FFN49V-18-1\&_cdi=13109\&_user=616147\&_orig=browse\&_coverDate=02\%2F01\%2F2005\&_sk=998819999\&view=c\&wchp=dGLbVlz-zSkzV\&md5=1cd6a1fcf1599d96b97a2e45a181c0e5\&ie=/sdarticle.pdf},
	author = {Therese Berg and Bengt Jonsson and Martin Leucker and Mayank Saksena}
}
Postscript: