Determinization of conditional term rewriting systems

被引：5

作者：

Nagashima, Masanori ^{[1
]}

Sakai, Masahiko ^{[1
]}

Sakabe, Toshiki ^{[1
]}

机构：

[1] Nagoya Univ, Grad Sch Informat Sci, Chikusa Ku, Nagoya, Aichi 4648603, Japan

来源：

THEORETICAL COMPUTER SCIENCE | 2012年 / 464卷

关键词：

Deterministic conditional term rewriting system; Functional program; Rule-based transformation; UNFOLD FOLD TRANSFORMATION; PROGRAM INVERSION; LOGIC; TERMINATION; RULES; CORRECTNESS; STRATEGIES; INVERTER;

D O I：

10.1016/j.tcs.2012.09.005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper discusses determinization of conditional term rewriting systems with oriented constructor rules. We present a rule-based transformation system, which transforms a non-deterministic one into a deterministic one, together with examples of the transformation. We prove that the transformation system is simulation sound and simulation complete. We also prove that the transformation system is complete for some class by introducing a strategy for the transformation system. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：72 / 89

页数：18

共 41 条

[1]

Almendros-Jiménez JM, 2007, LECT NOTES COMPUT SC, V4449, P253

[2] Rules plus strategies for transforming lazy functional logic programs [J].

Alpuente, M ;

Falaschi, M ;

Moreno, G ;

Vidal, G .

THEORETICAL COMPUTER SCIENCE, 2004, 311 (1-3) :479-525

[3] Termination of term rewriting using dependency pairs [J].

Arts, T ;

Giesl, J .

THEORETICAL COMPUTER SCIENCE, 2000, 236 (1-2) :133-178

[4]

Baader F., 1998, Term rewriting and all that

[5] Transforming constraint logic programs [J].

Bensaou, N ;

Guessarian, I .

THEORETICAL COMPUTER SCIENCE, 1998, 206 (1-2) :81-125

[6] CONDITIONAL REWRITE RULES - CONFLUENCE AND TERMINATION [J].

BERGSTRA, JA ;

KLOP, JW .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1986, 32 (03) :323-362

[7] TRANSFORMATION SYSTEM FOR DEVELOPING RECURSIVE PROGRAMS [J].

BURSTALL, RM ;

DARLINGTON, J .

JOURNAL OF THE ACM, 1977, 24 (01) :44-67

[8] ORDERINGS FOR TERM-REWRITING SYSTEMS [J].

DERSHOWITZ, N .

THEORETICAL COMPUTER SCIENCE, 1982, 17 (03) :279-301

[9] Transformations of CLP modules [J].

Etalle, S ;

Gabbrielli, M .

THEORETICAL COMPUTER SCIENCE, 1996, 166 (1-2) :101-146

[10]

Fioravanti F., 2004, LECT NOTES COMPUTER, V3049, P77

← 1 2 3 4 5 →