Syntactic pattern recognition

Contents
Introductory Issues
1. Paradigmatic Considerations on Syntactic Pattern Recognition
1.1 Structure - Property of Natural Objects and Artifacts
1.2 Syntax - Rules to Arrange Well-Formed Structures
1.3 Syntactic Pattern Recognition: When and Why
1.3.1 Structure-Based Distinguishability of Objects
1.3.2 Reusability of Structural Subpatterns
1.3.3 Hierarchy-Oriented Multilevel Recognition
1.3.4 Requirement of Structure-Based Interpretation
2. Methodology of Syntactic Pattern Recognition
2.1 Structural Patterns: Strings, Trees and Graphs
2.2 Formal Tools: Grammars - Automata - Induction Algorithms
2.3 Place of Syntactic Pattern Recognition in Computer Science
String-based Models
3. Pattern Recognition Based on Regular and CF Grammars
3.1 Recognition with Finite-State Automata
3.2 Recognition of CF Languages
3.2.1 LL(k) Languages
3.2.2 LR(k) Languages
3.2.3 Precedence Parsing
3.2.4 Earley Parser
3.2.5 Cocke-Younger-Kasami Parser
3.2.6 Summary of Parsers for CF Languages
3.3 Recognition of Vague/Distorted Patterns
3.3.1 Stochastic Languages
3.3.2 Fuzzy Languages
3.3.3 Error-Correcting Parsing
3.3.4 Hidden Markov Model (HMM) and Viterbi Algorithm
4. Enhanced String-Based Models for Pattern Recognition
4.1 Grammars with Operator Controlled Derivations
4.1.1 Indexed and Linear Indexed Grammars
4.1.2 Head Grammars
4.1.3 Combinatory Categorial Grammars
4.1.4 Conjunctive and Boolean Grammars
4.1.5 Remarks on Mildly Context-Sensitive Grammars
4.2 Grammars with Programmed Derivations
4.2.1 Programmed Grammars
4.2.2 Dynamically Programmed Grammars
4.3 Augmented Regular Expressions
4.4 Attributed Grammars
4.5 Picture Languages
4.5.1 Picture Description Languages
4.5.2 Two-Dimensional Automata
4.5.3 Siromoney Matrix/Array Grammars
4.5.4 Shape Grammars
4.5.5 Shape Feature Languages
4.5.6 Remarks on Picture and Visual Languages
4.6 Timed Automata
5. Inference (Induction) of String Languages
5.1 Text Learning Methods for Regular Languages
5.1.1 Brzozowski-Derivative-Based Inference
5.1.2 k-Tail-Based Inference
5.1.3 Inference of k-Testable Languages
5.1.4 Inference of Reversible Regular Languages
5.2 Informed Learning Methods for Regular Languages
5.2.1 Gold-Trakhtenbrot-Bārzdiņš Model
5.2.2 Algorithm RPNI
5.3 Inference of Reversible CF Languages
5.4 Baum-Welch Learning of HMMs
5.5 Remarks on the Inference of String Languages
6. Applications of String Methods
6.1 Shape and Picture Analysis
6.2 Optical Character Recognition
6.3 Structure Analysis in Bioinformatics
6.4 Medical Image/Signal Analysis
6.5 Speech Recognition and NLP
6.6 Analysis of Visual Events and Activities
6.7 Signal Analysis for Process Monitoring and Control
6.8 Architectural Object Analysis
6.9 Feature Recognition for CAD/CAM
6.10 Structure Analysis in Chemistry
6.11 Radar Signal Analysis
6.12 Pattern Recognition in Seismology
6.13 Pattern Recognition in Geology
6.14 Fingerprint Recognition
6.15 Financial/Economics Time Series Analysis
6.16 Image Processing
6.17 Summary
Tree-based Models
7. Pattern Recognition Based on Tree Languages
7.1 Recognition of Expansive Tree Languages
7.2 Minimum-Distance SPECTA Model
7.3 Maximum-Likelihood SPECTA Model
7.4 Generalized Error-Correcting Tree Automata (GECTA)
7.5 Tree Adjoining Grammars
7.6 Remarks on Tree Languages
8. Inference (Induction) of Tree Languages
8.1 k-Tail-Based Inference of Tree Languages
8.2 Inference of Reversible Tree Languages
8.3 Tree-Derivative-Based Inference
8.4 Informed Learning of Tree Languages
8.5 Remarks on the Inference of Tree Languages
9. Applications of Tree Methods
9.1 Image Analysis and Processing
9.2 Optical Character Recognition
9.3 Structure Analysis in Bioinformatics
9.4 Texture Analysis
9.5 Analysis of Visual Events and Activities
9.6 Pattern Recognition in Seismology
9.7 Speech Recognition and NLP
9.8 Summary
Graph-based Models
10. Pattern Analysis with Graph Grammars
10.1 Bunke Attributed Programmed Graph Grammars
10.2 Shi-Fu Parser for Expansive Graph Languages
10.3 Sanfeliu-Fu Parser for Attributed Tree-Graph Grammars
10.4 Recognition of ETPL(k) and ETPR(k) Graph Languages
10.5 Recognition of Plex Languages
10.5.1 Bunke-Haller Parser
10.5.2 Peng-Yamamoto-Aoki Parser
10.6 And-Or Graph Model
10.7 Remarks on Graph Languages and Their Parsing
11. Inference (Induction) of Graph Languages
11.1 Inference of Expansive Graph Languages
11.2 Inference of ETPL(k) Graph Languages
11.2.1 Inference from IE Graph
11.2.2 Inference from a Sample of IE Graphs
11.3 Remarks on the Inference of Graph Languages
12. Applications of Graph Methods
12.1 Scene Analysis
12.2 Picture and Diagram Analysis
12.3 Feature Recognition for CAD/CAM
12.4 Analysis of Visual Events and Activities
12.5 Structure Analysis in Chemistry
12.6 Optical Character Recognition
12.7 Structure Analysis for Process Monitoring and Control
12.8 Structure Analysis in Bioinformatics and Medicine
12.9 Summary
Future of Syntactic Pattern Recognition
13. Summary of Results and Open Problems
13.1 Summary of Results
13.1.1 Theoretical Results
13.1.2 Application Results
13.2 Open Problems
14. Methodological Issues
14.1 General Methodological Principles
14.2 Model-Specific Methodological Recommendations
14.3 Concluding Remarks
Appendix A Formal Languages and Automata - Selected Notions
A.1 Chomsky’s String Grammars
A.2 String Automata
A.3 NLC Graph Grammars
Bibliography
Index

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.