ALGORITHMS FOR THE CONSTRAINED EDITING DISTANCE BETWEEN ORDERED LABELED TREES AND RELATED PROBLEMS

Authors
ZHANG KZ
Citation
Kz. Zhang, ALGORITHMS FOR THE CONSTRAINED EDITING DISTANCE BETWEEN ORDERED LABELED TREES AND RELATED PROBLEMS, Pattern recognition, 28(3), 1995, pp. 463-474
Citations number
22
Categorie Soggetti
Computer Sciences, Special Topics","Engineering, Eletrical & Electronic","Computer Science Artificial Intelligence
Journal title
Pattern recognition → ACNP
ISSN journal
00313203
Volume
28
Issue
3
Year of publication
1995
Pages
463 - 474
Database
ISI
SICI code
0031-3203(1995)28:3<463:AFTCED>2.0.ZU;2-0
Abstract
This paper considers the problem of computing a constrained editing di stance between ordered labeled trees. This distance metric can be appl ied to pattern recognition, syntactic tree comparison, classification tree comparison and other applications. The problem of approximate ord ered tree matching is also considered. We present optimal algorithms f or solving these problems in sequential time O(\T-1\ x \T-2\).