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 条

[11]

Jouannaud JP, 1995, LECT NOTES COMPUT SC, V968, P235

[12]

KENNAWAY JR, 1995, LNCS, V398, P247

[13] SEQUENTIALITY IN ORTHOGONAL TERM REWRITING-SYSTEMS [J].

KLOP, JW ;

MIDDELDORP, A .

JOURNAL OF SYMBOLIC COMPUTATION, 1991, 12 (02) :161-195

[14]

Klop JW, 1992, Handbook of Logik in Computer Science, V2, P1

[15]

MIDDELDORP A, 1997, P 24 ANN ACM SIGPLAN, P94, DOI DOI 10.1145/263699.263711

[16]

NAGAYA T, 1995, 918 RIMS U KYOT, P109

[17] NV-SEQUENTIALITY - A DECIDABLE CONDITION FOR CALL-BY-NEED COMPUTATIONS IN TERM-REWRITING SYSTEMS [J].

OYAMAGUCHI, M .

SIAM JOURNAL ON COMPUTING, 1993, 22 (01) :114-135

[18]

Thatcher J. W., 1968, Mathematical Systems Theory, V2, P57, DOI 10.1007/BF01691346

[19]

TOYAMA Y, 1992, PROCEEDINGS OF THE SEVENTH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, P274, DOI 10.1109/LICS.1992.185540

← 1 2 →