Identification of function distinguishable languages

AbstractWe show how appropriately chosen functions f which we call distinguishing can be used to make deterministic finite automata backward deterministic. This idea can be exploited to design regular language classes called f-distinguishable which are identifiable in the limit from positive samples. Special cases of this approach are the k-reversible and terminal distinguishable languages, as discussed in Angluin (J. Assoc. Comput. Mach. 29 (3) (1982) 741), Fernau (Technical Report WSI-99-23, Universität Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, 1999, Short version published in the proceedings of AMAI 2000, see \tt http://rutcor.rutgers.edu/~amai/aimath00/AcceptedCont.htm, Proc. 15th Internat. Conf. on Pattern Recognition (ICPR 2000), Vol. 2, IEEE Press, New York, 2000, pp. 125–128), Radhakrishnan (Ph.D. Thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, India, 1987), Radhakrishnan and Nagaraja (IEEE Trans. Systems, Man Cybernet. 17 (6) (1987) 982). Moreover, we show that all regular languages may be approximated in the setting introduced by Kobayashi and Yokomori (in: K. P. Jantke, T. Shinohara, Th. Zeugmann (Eds.), Proc. Sixth Internat. Conf. Algorithmic Learning Theory (ALT’95), Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, Vol. 997, Springer, Berlin, 1995, pp. 298–312), (Theoret. Comput. Sci. 174 (1997) 251–257) by any class of f-distinguishable languages. Observe that the class of all function-distinguishable languages is equal to the class of regular languages