A New Heuristic for Inferring Regular Grammars
- 1 March 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. PAMI-3 (2), 191-197
- https://doi.org/10.1109/tpami.1981.4767078
Abstract
Modifications to a grammatical inference scheme by Feldman et al. are presented. A comparison of the relative performance of the original and modified schemes is made using the complexity measures of Feldman and Wharton. The case where a complex model is used to generate the sample set is then analyzed. A set of 104 samples was found that trained the program to infer the grammar that corresponded to the original model. The results of a study of the performance of this algorithm when there is a large number of samples is then presented. The major conclusion of this study is that the modified scheme has a superior performance on small sample sets but is highly unsuitable for large ones.Keywords
This publication has 7 references indexed in Scilit:
- Inference of Sequential Machines from Sample ComputationsIEEE Transactions on Computers, 1978
- Grammar enumeration and inferenceInformation and Control, 1977
- Grammatical Inference: Introduction and Survey - Part IIIEEE Transactions on Systems, Man, and Cybernetics, 1975
- Grammatical Inference: Introduction and Survey - Part IIEEE Transactions on Systems, Man, and Cybernetics, 1975
- On the Synthesis of Finite-State Machines from Samples of Their BehaviorIEEE Transactions on Computers, 1972
- GRAMMATICAL COMPLEXITY AND INFERENCEPublished by Defense Technical Information Center (DTIC) ,1969
- Language identification in the limitInformation and Control, 1967