Inference of Reversible Languages
Dana Angluin · Journal of the ACM · 1982
A famdy of efficient algorithms for referring certain subclasses of the regular languages from fmtte posttwe samples is presented These subclasses are the k-reversible languages, for k = 0, 1, 2, ....For each k there is an algorithm for finding the smallest k-reversible language containing any fimte posluve sample.It ts shown how to use this algorithm to do correct identification m the ILmlt of the kreversible languages from posmve data A reversible language is one that Is k-reverstble for some k __ 0. An efficient algonthrn is presented for mfernng reversible languages from posmve and negative examples, and it is shown that it leads to correct identification m the hmlt of the class of reversible languages.Numerous examples are gtven to dlustrate the algorithms and their behawor Categories and Subject Descriptors F 1 1 [Computation by Abstract Devices] Models of ComputaUon-automata, F 4 3 [Mathematical Logic and Formal Languages] Formal Languages--classes defined by grammars or automata; 1 2 6 [Artificial Intelligence] Learnmg--mductlon, 1.5 1 [Pattern Recognition] Models--structural