Decidable call by need computations in term rewriting (extended abstract)

被引：0

作者：

Durand, I ^{[1
]}

Middeldorp, A

机构：

[1] Univ Bordeaux 1, LaBRI, F-33405 Talence, France

[2] Univ Tsukuba, Inst Informat Sci & Elect, Tsukuba, Ibaraki 305, Japan

来源：

AUTOMATED DEDUCTION - CADE-14 | 1997年 / 1249卷

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper we study decidable approximations to call by need computations to normal and root-stable forms in term rewriting. We obtain uniform decidability proofs by making use of elementary tree automata techniques. Surprisingly, by avoiding complicated concepts like index and sequentiality we are able to cover much larger classes of term rewriting systems.

引用

页码：4 / 18

页数：15

共 19 条

[1]

[Anonymous], HDB THEORETICAL COMP

[2]

COMMON H, 1995, P 10 LICS, P508

[3]

COQUIDE JL, 1990, LECT NOTES COMPUT SC, V464, P120

[4] DECIDABILITY OF THE CONFLUENCE OF FINITE GROUND TERM REWRITE SYSTEMS AND OF OTHER RELATED TERM REWRITE SYSTEMS [J].

DAUCHET, M ;

HEUILLARD, T ;

LESCANNE, P ;

TISON, S .

INFORMATION AND COMPUTATION, 1990, 88 (02) :187-201

[5]

DAUCHET M, 1985, LECT NOTES COMPUT SC, V199, P80

[6]

Dershowitz Nachum, 1990, Handbook of Theoretical Computer Science, P243

[7]

Doner J., 1970, J. Comput. Syst. Sci., V4, P406

[8]

Gecseg F., 1984, Tree automata

[9]

HUET G, 1991, COMPUTATIONAL LOGIC, P396

[10]

Jacquemard F, 1996, LECT NOTES COMPUT SC, V1103, P362

← 1 2 →