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
StatePublished - Dec 1 1982

Fingerprint

Pattern Analysis
Parsing
Syntactics
Transducer
Transducers
Tree Automata
Minimum Distance
Motion
Syntax
Modeling

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

@article{38ceb443b79d4275821746405ba13d62,
title = "Conversion and parsing of tree transducers for syntactic pattern analysis",
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.",
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",
author = "Lin, {Wei Chung} and Fu, {King Sun}",
year = "1982",
month = "12",
day = "1",
doi = "10.1007/BF00996819",
language = "English (US)",
volume = "11",
pages = "417--458",
journal = "International Journal of Parallel Programming",
issn = "0885-7458",
publisher = "Springer New York",
number = "6",

}

Conversion and parsing of tree transducers for syntactic pattern analysis. / Lin, Wei Chung; Fu, King Sun.

In: International Journal of Computer & Information Sciences, Vol. 11, No. 6, 01.12.1982, p. 417-458.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Conversion and parsing of tree transducers for syntactic pattern analysis

AU - Lin, Wei Chung

AU - Fu, King Sun

PY - 1982/12/1

Y1 - 1982/12/1

N2 - 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.

AB - 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.

KW - bottom-up tree transducer

KW - generalized finite-state transformation

KW - generalized syntax-directed translation

KW - generalized syntax-directed tree translation

KW - grammatical inference

KW - human motion modeling

KW - minimum-distance structure-preserved error-correcting parser

KW - motion analysis

KW - Syntactic pattern recognition

KW - top-down backtrack parsing

KW - top-down tree transducer

KW - tree

KW - tree grammar

UR - http://www.scopus.com/inward/record.url?scp=0020297337&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020297337&partnerID=8YFLogxK

U2 - 10.1007/BF00996819

DO - 10.1007/BF00996819

M3 - Article

AN - SCOPUS:0020297337

VL - 11

SP - 417

EP - 458

JO - International Journal of Parallel Programming

JF - International Journal of Parallel Programming

SN - 0885-7458

IS - 6

ER -