Syntactic Pattern Recognition

Mariusz Flasiński

• Publisher: WSPC
• Year: 2019
• ISBN:
  9789813278486
• Topic: Computer Science
• Subtopic: Computer Vision & Pattern Recognition
• Index: Computer Science

This unique compendium presents the major methods of recognition and learning used in syntactic pattern recognition from the 1960s till 2018. Each method is introduced firstly in a formal way. Then, it is explained with the help of examples and its algorithms are described in a pseudocode. The survey of the applications contains more than 1,000 sources published since the 1960s. The open problems in the field, the challenges and the determinants of the future development of syntactic pattern recognition are discussed.

This must-have volume provides a good read and serves as an excellent source of reference materials for researchers, academics, and postgraduate students in the fields of pattern recognition, machine perception, computer vision and artificial intelligence.

Contents:

• Preface
• Nomenclature
• Introductory Issues:
  • Paradigmatic Considerations on Syntactic Pattern Recognition
  • Methodology of Syntactic Pattern Recognition
• String-Based Models:
  • Pattern Recognition Based on Regular and CF Grammars
  • Enhanced String-Based Models for Pattern Recognition
  • Inference (Induction) of String Languages
  • Applications of String Methods
• Tree-Based Models:
  • Pattern Recognition Based on Tree Languages
  • Inference (Induction) of Tree Languages
  • Applications of Tree Methods
• Graph-Based Models:
  • Pattern Analysis with Graph Grammars
  • Inference (Induction) of Graph Languages
  • Applications of Graph Methods
• Future of Syntactic Pattern Recognition:
  • Summary of Results and Open Problems
  • Methodological Issues
  • Appendix: Formal Languages and Automata — Selected Notions
• Bibliography
• Index

Readership: Professionals, researchers, academics, and postgraduate students in pattern recognition, image analysis, machine perception, computer vision and artificial intelligence.Syntactic Pattern Recognition;Computer Vision;Pattern Recognition00

PART 2

STRING-BASED MODELS

Chapter 3

Pattern Recognition Based on Regular and CF Grammars

String-based models of syntactic pattern recognition are defined with the help of Chomsky’s generative grammars¹ [Chomsky (1956, 1959, 1965)]. According to the Chomsky hierarchy, these grammars can be divided into four types depending on their generative power. Since the notion of the generative power of a type of grammar is crucial in syntactic pattern recognition (not only for Chomsky’s string grammars), we shall introduce it now.

Let L(G) be a language generated by a grammar G. Let X denote a type of grammars. The corresponding class X of languages constitutes the set

That is,

(X) is the set of all the languages L which can be generated by any grammar G of the class X. We say that grammars of a type X have greater generative power than grammars of a type Y iff

(Y) ⊊

(X).

Let UNR, CSG, CFG and REG denote the following types of Chomsky’s grammars: unrestricted, context-sensitive, context-free and regular, respectively. The following theorem establishes the Chomsky hierarchy.²

Theorem 3.1 (Chomsky Hierarchy [Chomsky (1959)])

A formal grammar is the generator of a set of pattern structural representations³ in syntactic pattern recognition, whereas a formal automaton is used for recognizing/accepting these representations. The following four types of formal automata⁴ are recognizers of languages generated by Chomsky’s grammars: a Turing machine, TM [Turing (1937)], a linear-bounded automaton, LBA [Myhill (1960); Kuroda (1964)], a pushdown automaton, PDA [Chomsky (1962)] and a finite-state automaton, FSA [Shannon (1948); Kleene (1956); Chomsky and Miller (1958); Rabin and Scott (1959)]. Now, let us denote a set of all the languages L which can be accepted/recognized by an automaton A of a class X with

(X). The following theorem establishes the correspondence between grammars and automata [Chomsky (1959, 1962); Bar-Hillel et al. (1961); Schützenberger (1963); Landweber (1963); Davis (1958)].

Fig. 3.1 The relations among the classes of string languages.

Theorem 3.2 (Grammars - Automata Correspondence)

On the basis of both theorems we can define the diagram which presents the relations among the classes of languages generated by Chomsky’s grammars and the classes of languages accepted/recognized by corresponding automata as in Fig. 3.1.

Although unrestricted and context-sensitive grammars are of great generative power, they are not used in syntactic pattern recognition because the corresponding automata, i.e. TM and LBA, are inefficient computationally. Therefore, in Sec. 3.1 and 3.2 ideas of constructing syntactic pattern recognition models which are based on regular and context-free grammars are introduced. The extensions of such models for the recognition of vague/distorted patterns are presented in Sec. 3.3. All the notions and denotations of formal language theory used in this chapter are introduced in Appendix A.

Fig. 3.2 Representation of the object with Freeman chain codes.

3.1 Recognition with Finite-State Automata

As we have mentioned in Chap. 2, a syntactic pattern recognition model consists of three basic formalisms: a grammar, a syntax analyzer and a language inference algorithm. Additionally, for generating a parser control table on the basis of a set of grammar productions a parser generator is needed. The issue of a parser control generation is a standard problem of compiler design theory. Therefore, we present the issue only for finite-state automata in this section and for LL(k) parsers in the nex...

Table of contents

• Cover page
• Title page
• Copyright
• Dedication
• Preface
• Nomenclature
• Contents
• Introductory Issues
• String-based Models
• Tree-based Models
• Graph-based Models
• Future of Syntactic Pattern Recognition
• Appendix A Formal Languages and Automata - Selected Notions
• Bibliography
• Index