Error-Correcting Tree Automata for Syntactic Pattern Recognition
- 1 November 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-27 (11), 1040-1053
- https://doi.org/10.1109/tc.1978.1674993
Abstract
The syntax errors on trees are defined in terms of five types of error transformations, namely, substitution, stretch, split, branch, and deletion. The distance between two trees is the least cost sequence of error transformations needed to transform one to the other. Based on this definition, a class of error-correcting tree automata (ECTA) is proposed. The operation of ECTA is illustrated by a character recognition example.Keywords
This publication has 23 references indexed in Scilit:
- A syntactic approach to texture analysisComputer Graphics and Image Processing, 1978
- Decoding for channels with insertions, deletions, and substitutions with applications to speech recognitionIEEE Transactions on Information Theory, 1975
- Syntax-directed least-errors analysis for context-free languagesCommunications of the ACM, 1974
- Stochastic grammars and languagesInternational Journal of Parallel Programming, 1972
- Linear and Context-Free Graph GrammarsJournal of the ACM, 1972
- Mappings and grammars on treesTheory of Computing Systems, 1970
- Spelling correction in systems programsCommunications of the ACM, 1970
- Tree generating regular systemsInformation and Control, 1969
- A formal picture description scheme as a basis for picture processing systemsInformation and Control, 1969
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theoryJournal of Computer and System Sciences, 1967