On the structural grammatical inference problem for some classes of context-free grammars

DOI10.1016/0020-0190(92)90124-EMaRDI QIDQ1198013zbMATH OpenFDO

Authors Erkki Mäkinen

Publication date 16 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90124-E

zbMATH Keywords

analysis of algorithmsinvertible grammarsreversible context-free grammarstructural grammatical inference problem for reversible grammarstime complexity

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Review text

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.

Recommendations

• Remarks on the structural grammatical inference problem for context-free grammars
• Efficient learning of context-free grammars from positive structural examples
• A local search algorithm for grammatical inference
• Grammatical Inference: Algorithms and Applications
• Inferring pure context-free languages from positive data

Cites work

• Efficient learning of context-free grammars from positive structural examples
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• Inductive inference of formal languages from positive data
• Inference of Reversible Languages
• Learning context-free grammars from structural data in polynomial time
• The grammatical inference problem for the Szilard languages of linear grammars
• Worst-case Analysis of Set Union Algorithms

Cited in

(4)

• Remarks on the structural grammatical inference problem for context-free grammars
• Recent advances of grammatical inference
• scientific article; zbMATH DE number 4114091 (Why is no real title available?)
• Grammatical inference: An old and new paradigm

This page was built for publication: On the structural grammatical inference problem for some classes of context-free grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198013)