Inference of Reversible Languages

Abstract

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