Error correcting analysis for tree languages

被引：8

作者：

López, D ^{[1
]}

Sempere, JM ^{[1
]}

García, P ^{[1
]}

机构：

[1] Univ Politecn Valencia, Dept Sistemas Informat & Computac, E-46071 Valencia, Spain

来源：

INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE | 2000年 / 14卷 / 03期

关键词：

tree languages; editing distance; error correcting parsing; tree automata;

D O I：

10.1142/S0218001400000234

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

To undertake a syntactic approach to a pattern recognition problem, it is necessary to have good grammatical models as well as good parsing algorithms that allow distorted samples to be classified. There are several methods that obtain, by taking two trees as input, the editing distance between them. In the following work, a polynomial time algorithm which processes the distance between a tree and a tree automaton is presented. This measure can be used in pattern recognition problems as an error model inside a syntactic classifier.

引用

页码：357 / 368

页数：12

共 17 条

[1]

Bunke H., 1990, SYNTACTIC STRUCTURAL

[2]

Fu K. S., 1982, SYNTACTIC PATTERN RE

[3]

GARCIA P, 1993, II461993 DSIC U POL

[4]

GARCIA P, 1993, II471993 DSIC U POL

[5]

Kobayashi S, 1994, P 5 GEN INF WORKSH, VV, P29

[6] ERROR-CORRECTING TREE AUTOMATA FOR SYNTACTIC PATTERN-RECOGNITION [J].

LU, SY ;

FU, KS .

IEEE TRANSACTIONS ON COMPUTERS, 1978, 27 (11) :1040-1053

[7]

OOMMEN BJ, 1996, IEEE T COMPUT, V45, P11

[8]

OOMMEN BJ, 1998, LNCS, V1451, P169

[9] EFFICIENT LEARNING OF CONTEXT-FREE GRAMMARS FROM POSITIVE STRUCTURAL EXAMPLES [J].

SAKAKIBARA, Y .

INFORMATION AND COMPUTATION, 1992, 97 (01) :23-60

[10] LEARNING CONTEXT-FREE GRAMMARS FROM STRUCTURAL DATA IN POLYNOMIAL-TIME [J].

SAKAKIBARA, Y .

THEORETICAL COMPUTER SCIENCE, 1990, 76 (2-3) :223-242

← 1 2 →