This book was written to provide students, engineers, and scientists involved in pattern recognition, digital image processing, and artificial intelligence with a comprehensive introduction to the concepts and techniques of syntactic pattern recognition.
Syntactic pattern recognition is concerned with the application of formal language and automata theory to the modeling and description of structural relationships in pattern classes. This is in contrast with classical decision-theoretic methods, in which recognition is generally performed on a strictly quantitative basis without explicit use of structural information. The capability for describing structure is particularly important in pictorial pattern recognition, scene analysis, and other applications where primitive elements and their relationships are essential characteristics.
The origin of formal language theory may be traced to the middle 19508 with the development by Noam Chomsky of mathematical models of grammars related to his work in natural languages. One of the original goals of linguists working in this area was to develop computational models of grammars capable of describing natural languages such as English and French. The hope was that, if this could be done, it would be a relatively simple matter to "teach" computers to interpret natural languages for the purposes of translation and problem solving. Although it is generally agreed that these expectations have been unrealized thus far, spin-offs and extensions of the research in this area have had a significant impact on other fields, such as compiler design, programming languages, automata theory, and pattern recognition. Applications of formal languages in the latter area followed shortly after Chomsky's initial developments, with results on automated analysis of alphanumeric characters and human chromosomes appearing in the early 1960s. Since these initial applications, syntactic pattern recognition has experienced vigorous growth as a subject of interdisciplinary study and research in such fields as engineering, computer science, information science, physics, chemistry, biology, medicine, and applied mathematics.
Most of the material dealing with syntactic pattern recognition theory and applications has been widely scattered in various technical journals, conference proceedings, and advanced monographs. Consequently, it is a rather difficult and time-consuming task, particularly for a newcomer to this interdisciplinary area, to extract from the large volume of available literature the wide range of principles underlying the subject matter. The principal objectives of this book are to provide an introduction to basic concepts and techniques of syntactic pattern recognition and to lay a foundation that can be used as the basis for further study and research in this field. To achieve these objectives, we have focused attention on material which we feel is fundamental and for which the scope of applications is not limited to specialized problems. The presentation emphasizes practical rather than strictly theoretical aspects, and numerous examples are provided to illustrate the principles developed in the text. Most of the topics covered in the book have been taught by the authors in first-year graduate courses at the University of Tennessee. We have also included revised material presented in short courses and seminars. The mathematical level is well within the grasp of seniors in a technical discipline, such as engineering and computer science, which requires introductory preparation in mathematics and probability.