Characteristic Sets for Learning K-Acceptable Languages

Learnability of languages is a challenging problem in the domain of formal language identification. It is known that the efficiency of a learning technique can be measured by the size of some good samples (representative or distinctive samples) formally called a characteristic set. The authors' research focuses on the characteristic set of k-acceptable languages. They proposed a Gold-style learning algorithm called KRPNI which applied the grammatical inference technique to identify a language and expressed it by a k-DFA. In this paper, they study the existence of such characteristic sets.