On the structural grammatical inference problem for some classes of context-free grammars (Q1198013): Difference between revisions

Inference from positive data is strictly less powerful than inference from positive and negative data [\textit{D. Anglnin}, Inform. and Control 45, 117-135 (1980; Zbl 0459.68051)]. As a method for compensating for the lack of negative data, \textit{Y. Sakakibara} [Theor. Comput. Sci. 76, No. 2/3, 223-242 (1990; Zbl 0704.68067); Inf. Comput. 97, No. 1, 23-60 (1992; Zbl 0764.68051)] has considered the problem of inferring context-free grammars from structural information. Given a finite positive sample, i.e. a set of words belonging to the language generated by the grammar in question, and the derivation trees of the works with unlabelled internal nodes, Sakakibara's algorithm finds out the reversible context-free grammar consistent with the sample. In other words, Sakakibara's algorithm solves the structural grammatical inference problem for reversible grammars. The purpose of this paper is twofold. First, we consider the time complexity of Sakakibara's algorithm. Second, we introduce a new class of context-free grammars, called type invertible grammars, and consider the structural grammatical inference problem for this class of grammars. The class of type invertible grammars is a subclass of reversible grammars.