Optimizing Linear Recursive Formulas by Detaching Isolated Variables
Summary :
Program transformation is a kind of optimization techniques for logic programs, which aims at transforming equally a program into an other form by exploiting some properties or information of the program, so as to make the program cheaper to evaluate. In this paper, a new kind of property of logic programs, called reducibility, is exploited in program transformation. A recursive predicate is reducible if the values of some variables in the recursive predicate are independent to the remainder part and can be detached from the predicate after finite times of expansions. After being proved that the semantic notion of reducibility can be replaced by the syntactic notion of disconnectivity of a R-graph, which is a kind of graph model to represent the behavior of formula expansions, an efficient testing and factoring algorithm is proposed. The paper also extends some existed results on compiled formulas of linear sirups, and compares with some related work.
- Publication
- IEICE TRANSACTIONS on Information Vol.E78-D No.5 pp.579-585
- Publication Date
- 1995/05/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Databases
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Xiaoyong DU, Naohiro ISHII, "Optimizing Linear Recursive Formulas by Detaching Isolated Variables" in IEICE TRANSACTIONS on Information,
vol. E78-D, no. 5, pp. 579-585, May 1995, doi: .
Abstract: Program transformation is a kind of optimization techniques for logic programs, which aims at transforming equally a program into an other form by exploiting some properties or information of the program, so as to make the program cheaper to evaluate. In this paper, a new kind of property of logic programs, called reducibility, is exploited in program transformation. A recursive predicate is reducible if the values of some variables in the recursive predicate are independent to the remainder part and can be detached from the predicate after finite times of expansions. After being proved that the semantic notion of reducibility can be replaced by the syntactic notion of disconnectivity of a R-graph, which is a kind of graph model to represent the behavior of formula expansions, an efficient testing and factoring algorithm is proposed. The paper also extends some existed results on compiled formulas of linear sirups, and compares with some related work.
URL: https://global.ieice.org/en_transactions/information/10.1587/e78-d_5_579/_p
Copy
@ARTICLE{e78-d_5_579,
author={Xiaoyong DU, Naohiro ISHII, },
journal={IEICE TRANSACTIONS on Information},
title={Optimizing Linear Recursive Formulas by Detaching Isolated Variables},
year={1995},
volume={E78-D},
number={5},
pages={579-585},
abstract={Program transformation is a kind of optimization techniques for logic programs, which aims at transforming equally a program into an other form by exploiting some properties or information of the program, so as to make the program cheaper to evaluate. In this paper, a new kind of property of logic programs, called reducibility, is exploited in program transformation. A recursive predicate is reducible if the values of some variables in the recursive predicate are independent to the remainder part and can be detached from the predicate after finite times of expansions. After being proved that the semantic notion of reducibility can be replaced by the syntactic notion of disconnectivity of a R-graph, which is a kind of graph model to represent the behavior of formula expansions, an efficient testing and factoring algorithm is proposed. The paper also extends some existed results on compiled formulas of linear sirups, and compares with some related work.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Optimizing Linear Recursive Formulas by Detaching Isolated Variables
T2 - IEICE TRANSACTIONS on Information
SP - 579
EP - 585
AU - Xiaoyong DU
AU - Naohiro ISHII
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E78-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 1995
AB - Program transformation is a kind of optimization techniques for logic programs, which aims at transforming equally a program into an other form by exploiting some properties or information of the program, so as to make the program cheaper to evaluate. In this paper, a new kind of property of logic programs, called reducibility, is exploited in program transformation. A recursive predicate is reducible if the values of some variables in the recursive predicate are independent to the remainder part and can be detached from the predicate after finite times of expansions. After being proved that the semantic notion of reducibility can be replaced by the syntactic notion of disconnectivity of a R-graph, which is a kind of graph model to represent the behavior of formula expansions, an efficient testing and factoring algorithm is proposed. The paper also extends some existed results on compiled formulas of linear sirups, and compares with some related work.
ER -
English
