Syntactic/semantic techniques in pattern recognition: A survey

This paper surveys some of the contemporary work in syntactic/semantic pattern recognition, with emphasis on four topics that are active research areas. These areas-grammatical inferrence, probabilistic models, syntactic errorcorrection, and grammars with attributes-present challenging questions both as to theory and as to practice.Portions of the paper are adapted from Syntactic Methods in Pattern Recognition, M. G. Thomason, to appear in theProceedings of the NATO Advanced Study Institute, Oxford University, 1981 J. Kittler, Ed. (D. Reidel Publishing Company. Dordrecht, Holland).     

The problem of finding a semantic strategy for focusing inference rules

This article is the fifteenth of a series of articles discussing various open research problems in automated reasoning. Here we focus on finding a strategy — other than a simple syntactic one — that can be used for focusing the attention of the inference rule(s) in use. The problem proposed for research asks one to find semantic criteria for selecting the clauses needed to complete the application of an inference rule. Suggestions for test problems are included. We note that Yuan Yu has solved two of these problems using a rather different approach with the Boyer-Moore theorem prover; his work is reported elsewhere in this issue of the Journal of Automated Reasoning.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Conversion and parsing of tree transducers for syntactic pattern analysis

The conversion algorithms for two classes of tree transducers, i.e., simple generalized syntax-directed tree translation (SGSDTT) and generalized finite state transformation (GFST), are proposed. A top-down backtrack parsing algorithm for a GFST is presented. The minimum distance structure-preserved error-correcting tree automaton is also extended to be a parser for SGSDTT. Finally, the tree transducers are applied to modeling and analysis of human motion.This work was supported by the NSF Grant IST 79-18884.