Grammatical Inference: Introduction and Survey - Part I
IEEE Transactions on Systems Man and CyberneticsPublished 1 January 1975
King‐Sun Fu, Taylor L. Booth
Citations272
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
The problem of grammatical inference is introduced, and its potential engineering applications are demonstrated. Inference algorithms for finite-state and context-free grammars are presented. The application of some of the algorithms to the inference of pattern grammars in syntactic pattern recognition is illustrated by examples.
Keywords
Computer Science
IEEE Transactions on Systems Man and CyberneticsOutline of a New Approach to the Analysis of Complex Systems and Decision Processes
8,667 Citations1973Lotfi A. Zadeh
By relying on the use of linguistic variables and fuzzy algorithms, the approach provides an approximate and yet effective means of describing the behavior of systems which are too complex or too ill-defined to admit of precise mathematical analysis.
Information and ControlLanguage identification in the limit
3,569 Citations1967Eric Gold
It was found that theclass of context-sensitive languages is learnable from an informant, but that not even the class of regular languages is learningable from a text.
Information and ControlA formal theory of inductive inference. Part II
1,786 Citations1964Ray J. Solomonoff
Four ostensibly different theoretical models of induction are presented, in which the problem dealt with is the extrapolation of a very long sequence of symbols—presumably containing all of the information to be used in the induction.
Information and ControlA formal theory of inductive inference. Part I
1,149 Citations1964Ray J. Solomonoff
Nuclear Science and EngineeringFormal Languages and their Relation to Automata
1,004 Citations1970James B. Morris
IEEE Transactions on ComputersOn the Synthesis of Finite-State Machines from Samples of Their Behavior
496 Citations1972Alan W. Biermann, Jerome A. Feldman
The Nerode realization technique for synthesizing finite-state machines from their associated right-invariant equivalence relations is modified to give a method for synthesizer machines from finite subsets of their input-output behavior.
Journal of Computer and System SciencesTree acceptors and some of their applications
494 Citations1970John Doner
It is shown here that the weak secondorder theory of two successors is decidable, thus settling a problem of Buchi, and this result is applied to obtain positive solutions to the decision problems for various other theories, e.g., the weaksecond-order theories of order types built up from the finite types.
Communications of the ACMReport on the algorithmic language ALGOL 60
493 Citations1960John Backus, Friedrich L. Bauer +10 more
It was decided to hold an international meeting in January 1960 for improving the ALGOL language and preparing a final report, and seven representatives were selected to attend the January 1960 international conference.
IEEE Transactions on ComputersApplying Probability Measures to Abstract Languages
232 Citations1973Taylor L. Booth, Richard A. Thompson
The problem of assigning a probability to each word of a language is considered and two methods are discussed.
Information and ControlTree generating regular systems
225 Citations1969Walter S. Brainerd
The main result is that the sets of trees generated by regular systems are exactly those that are accepted by tree automata.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)A study of grammatical inference
220 Citations1969James J. Horning
Communications of the ACMTranslator writing systems
199 Citations1968Jerome A. Feldman, David Gries
A critical review of recent efforts to automate the writing of translators of programming languages is presented and various approaches to automating the postsyntactic aspects of translator writing are discussed.
Communications of the ACMA syntax directed compiler for ALGOL 60
195 Citations1983Edgar T. Irons
A compiling system which essentially separates the functions of defining the language and translating it into another and it is demonstrated heuristically that the proposed meta-language does suffice to specify a translation for any language it can describe.
Information and ControlSome decidability results on grammatical inference and complexity
176 Citations1972Jerome A. Feldman
The problem of grammatical inference is considered and a number of positive answers to decidability questions obtained.
Communications of the ACMA syntax directed compiler for ALGOL 60
163 Citations1961Edgar T. Irons
The author's algorithm is indebted to Arthur Anger, presently at Harvard University, for many helpful criticisms and suggestions, and for coding the algorithm on the UNiwxc 1105.
Information and ControlOn the entropy of context-free languages
142 Citations1970Werner Kuich
The information theoretical concept of the entropy (channel capacity) of context-free languages and its relation to the structure generating function is investigated and theorems on the convergence parameter of infinite matrices are proved and applied to the evaluation of theropy of certain context- free languages.
IEEE Transactions on ComputersTree Systems for Syntactic Pattern Recognition
118 Citations1973King‐Sun Fu, Bharat Bhargava
An approach of representing patterns by trees rather than by strings is described, and the tree system is applied to the problem of syntactic pattern recognition.
Probabilistic representation of formal languages
95 Citations1969Taylor L. Booth
It is shown that under some conditions it is possible to recognize a non finitestate language with a finite state acceptor if one is willing to accept a small probability of making an error.
Computer Graphics and Image ProcessingLinguistic Methods for the Description of a Straight Line on a Grid
94 Citations1974R. Brons
This paper describes the construction of strings representing straight lines in an arbitrary direction on a grid and compares some grammatical systems that generate these strings and compares them to Lindenmayer grammars, which are quite useless but still very convenient.
Probabilistic Grammars for Natural Languages
90 Citations1972Patrick Suppes
Elsevier eBooksA SURVEY OF RESULTS IN GRAMMATICAL INFERENCE
87 Citations1972Alan W. Biermann, Jerome A. Feldman
IEEE Transactions on Electronic ComputersThe Syntax of Programming Languages-A Survey
84 Citations1964Robert W. Floyd
The syntactic rules for many programming languages have been expressed by formal grammars, generally variants of phrase-structure grammar, but major problems remain in rendering analyzers efficient in use of space and time and in finding fully satisfactory formal Grammars for present and future programming languages.
GRAMMATICAL COMPLEXITY AND INFERENCE
68 Citations1969Jerome A. Feldman, James Gips +2 more
Several notions of grammatical complexity and their properties are studied and the question of learning the least complex grammar for a set of strings is investigated leading to a variety of positive and negative results.
IEEE Transactions on ComputersA Stochastic Syntax Analysis Procedure and Its Application to Pattern Classification
59 Citations1972H.C. Lee, King‐Sun Fu
Developed is a stochastic context-free language for use in pattern classification of chromosome images based on statistical decision theory with the probability of occurrence of each pattern computed from the stochastically context- free grammar.
IEEE Transactions on ComputersStochastic Syntactic Decoding for Pattern Classification
57 Citations1975Lai-Wo Fung, King‐Sun Fu
The maximum-likelihood criterion and the minimum-distance criterion are proposed for the classification of noisy strings described by context-free grammars and classification algorithms based on a modified Cocke-Younger-Kasami parsing scheme are presented.
Information and ControlApproximate language identification
54 Citations1974R.M. Wharton
A comparison of corresponding results for exact and approximate language identification yields two distinct ways in which the results for approximatelanguage identification are stronger than those for exact language identification.
Communications of the ACMThe use of grammatical inference for designing programming languages
50 Citations1973Stefano Crespi-Reghizzi, Michel A. Melkanoff +1 more
This work is proposing an interactive approach to the grammar design problem wherein the designer presents a sample of sentences and structures as input to a grammatical inference algorithm, which constructs a grammar which is a reasonable generalization of the examples submitted by the designer.
Pattern RecognitionStochastic programmed grammars for syntactic pattern recognition
48 Citations1972P. H. Swain, K. S. Fu
An algorithm for parsing strings generated by Stochastic Context-Free Programmed Grammars is described and an example is presented of one such grammar which generates “noisy” squares.
International Journal of Parallel ProgrammingStochastic grammars and languages
43 Citations1972K. S. Fu, Thomas S. Huang
This paper summarizes some recent results concerned with the extension of formal languages to their corresponding stochastic versions, and some decidability problems of stochastics (weighted, fuzzy) languages are discussed.
Pattern RecognitionAn application of stochastic languages to fingerprint pattern recognition
43 Citations1976Bijan Moayer, K. S. Fu
A stochastic syntactic approach for representation and classification of fingerprint patterns is presented and experimental results in terms of real data fingerprints are presented.
Information and ControlEntropies of probabilistic grammars
40 Citations1974Stephen Soule
How to maximize the information rate is shown, and the maximum is related to the classical notion of the capacity of a language.
Elsevier eBooksON SYNTACTIC PATTERN RECOGNITION AND STOCHASTIC LANGUAGES
33 Citations1972K. S. Fu
This chapter discusses syntactic pattern recognition and stochastic languages, with emphasis on the description of noisy and/or distorted patterns and the learning of grammar from the actual pattern samples.
Computer Graphics and Image ProcessingStochastic languages for picture analysis
29 Citations1973K. S. Fu
Stochastic syntax analysis procedures for the recognition of noisy patterns and a procedure for the estimation of production probabilities of a stochastic context-free language from sample strings are presented.
Journal of CyberneticsStochastic Automata, Stochastic Languages and Pattern Recognition
29 Citations1971K. S. Fuf
The potential application of stochastic languages for pattern description is demonstrated, and the possibility of employing Stochastic automata as pattern classifiers is discussed.
Information SystemsA Syntactic Pattern Recognition System with Learning Capability
26 Citations1974Han-ju Lee, K. S. Fu
Ch Chromosome aberrations induced by radiation exposure are identified through the use of the learning algorithm and stochastic syntax analysis.
ON THE SYNTHESIS OF FINITE-STATE ACCEPTORS
20 Citations1970Alan W. Biermann, Jerome A. Feldman
The paper gives a method for identifying a finite-statelanguage from a randomly chosen finite subset of the language if the subset is large enough and if a bound is known on the number of states required to recognizethe language.
IEEE Transactions on ComputersDetermination of Probabilistic Grammars for Functionally Specified Probability-Measure Languages
20 Citations1974Richard A. Thompson
This paper assumes that some finite representation exists for the set of words (this can be a nonprobabilistic grammar) and that the probability of each word in the language is computable by some word function whose domain is the language.
Computer Graphics and Image ProcessingStochastic syntactic analysis for programmed grammars and syntactic pattern recognition
20 Citations1972Thomas S. Huang, K. S. Fu
The class of stochastic context-free programmed grammars is shown to be quite effective in characterizing the structures of some pictorial patterns and to be better than that of the nondeterministic syntactic analyzer proposed earlier.
Minds at UW (University of Wisconsin)An interactive heuristic program for learning transformational grammars.
19 Citations1970Sheldon Klein, Michael A. Kuppin
IEEE Transactions on ComputersErrors in Regular Languages
17 Citations1974Michael G. Thomason
A method using operators for determining regular expressions defining error-corrupted strings is developed and is employed in the construction of a finite automaton, the outputs of which are stochastically generated by Bayes' Rule to take into account the frequencies with which strings appear as inputs and the probabilities of errors.
IEEE Transactions on Information TheoryMaximum-likelihood syntactic decoding
16 Citations1975Lai-Wo Fung, King‐Sun Fu
More errors in the strings coming out of the noisy channel can be corrected by the syntactic decoder using syntactic analysis than the !
Communications of the ACMFORTRAN IV as a syntax language
12 Citations1964B. M. Leavenworth
Any BNF system (context-free psg) can be mechanically placed in this special form (which I call standard form), preserving ambiguities (or lack thereof).
Communications of the ACMA grammar base question-answering procedure
12 Citations1967Peter S. Rosenbaum
A procedure for the automatic retrieval of certain segments of stored information through questions posed in natural language sentences through the use of a sentence recognition device for the class of grammars which will correctly decide between the grammatical and ungram-matical sentences of a natural language.
University of California, Los Angeles eBooksThe mechanical acquisition of precedence grammars
11 Citations1970Stefano Crespi-Reghizzi
The study presents a model and computer program which have practical value for some potential applications, and also some implications for child language learning.
IEEE Transactions on ComputersEstimation, Prediction, and Smoothing in Discrete Parameter Systems
10 Citations1970Taylor L. Booth
Using Bayes' theorem, the equations describing the ideal estimator, predictor, and smoother are developed and these equations are used to define an infinite-state Mealy-type sequential machine that performs these calculations.
International Journal of Parallel ProgrammingSequential syntactical decoding
7 Citations1974Flavio Roberte Dias Velasco, Celso de Renna e Souza
The minimum distance syntactical decoding algorithm of Souza and Scholtz is improved with the use of sequential decoding techniques, and Fano's algorithm is adapted to the syntacticals case.
National Technical Information Service eBooksStochastic syntactic analysis and syntactic pattern recognition
4 Citations1972Tian Huang, King Sun Fu
Stochastic syntactic analysis algorithms for the class of stochastic context-free programmed languages are proposed and their application to pattern classification demonstrated and the area of grammatical inference is briefly reviewed.