Conversion and parsing of tree transducers for syntactic pattern analysis

Wei Chung Lin*, King Sun Fu

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

The conversion algorithms for two classes of tree transducers, i.e., simple generalized syntax-directed tree translation (SGSDTT) and generalized finite state transformation (GFST), are proposed. A top-down backtrack parsing algorithm for a GFST is presented. The minimum distance structure-preserved error-correcting tree automaton is also extended to be a parser for SGSDTT. Finally, the tree transducers are applied to modeling and analysis of human motion.

Original languageEnglish (US)
Pages (from-to)417-458
Number of pages42
JournalInternational Journal of Computer & Information Sciences
Volume11
Issue number6
DOIs
Publication statusPublished - Dec 1 1982

    Fingerprint

Keywords

  • bottom-up tree transducer
  • generalized finite-state transformation
  • generalized syntax-directed translation
  • generalized syntax-directed tree translation
  • grammatical inference
  • human motion modeling
  • minimum-distance structure-preserved error-correcting parser
  • motion analysis
  • Syntactic pattern recognition
  • top-down backtrack parsing
  • top-down tree transducer
  • tree
  • tree grammar

ASJC Scopus subject areas

  • Engineering(all)

Cite this