Conversion and parsing of tree transducers for syntactic pattern analysis

Wei Chung Lin; King Sun Fu

doi:10.1007/BF00996819

Conversion and parsing of tree transducers for syntactic pattern analysis

Wei Chung Lin^*, King Sun Fu

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	417-458
Number of pages	42
Journal	International Journal of Computer & Information Sciences
Volume	11
Issue number	6
DOIs	https://doi.org/10.1007/BF00996819
State	Published - Dec 1 1982

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)

Access to Document

10.1007/BF00996819

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 = dec,

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",

}

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

SN - 0885-7458

VL - 11

SP - 417

EP - 458

JO - International Journal of Parallel Programming

JF - International Journal of Parallel Programming

IS - 6

ER -

Conversion and parsing of tree transducers for syntactic pattern analysis

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this