On the structural grammatical inference problem for some classes of context-free grammars (Q1198013): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q594603 |
||
Property / author | |||
Property / author: Erkki Maekinen / rank | |||
Revision as of 00:14, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the structural grammatical inference problem for some classes of context-free grammars |
scientific article |
Statements
On the structural grammatical inference problem for some classes of context-free grammars (English)
0 references
16 January 1993
0 references
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.
0 references
analysis of algorithms
0 references
reversible context-free grammar
0 references
structural grammatical inference problem for reversible grammars
0 references
time complexity
0 references
invertible grammars
0 references