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 tech-
niques of syntactic pattern recognition.
Syntactic pattern recognition is concerned with the application of formal
language and automata theory to the modeling and description of struc-
tural 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 1950s
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 lan-
guages 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 lan-
guages in the latter area followed shortly after Chomsky's initial develop-
ments, 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.