Computer Science – Symbolic Computation
Scientific paper
2000-11-28
Computer Science
Symbolic Computation
PhD Thesis in French
Scientific paper
This thesis is devoted to the study of a calculus that describes the application of conditional rewriting rules and the obtained results at the same level of representation. We introduce the rewriting calculus, also called the rho-calculus, which generalizes the first order term rewriting and lambda-calculus, and makes possible the representation of the non-determinism. In our approach the abstraction operator as well as the application operator are objects of calculus. The result of a reduction in the rewriting calculus is either an empty set representing the application failure, or a singleton representing a deterministic result, or a set having several elements representing a not-deterministic choice of results. In this thesis we concentrate on the properties of the rewriting calculus where a syntactic matching is used in order to bind the variables to their current values. We define evaluation strategies ensuring the confluence of the calculus and we show that these strategies become trivial for restrictions of the general rewriting calculus to simpler calculi like the lambda-calculus. The rewriting calculus is not terminating in the untyped case but the strong normalization is obtained for the simply typed calculus. In the rewriting calculus extended with an operator allowing to test the application failure we define terms representing innermost and outermost normalizations with respect to a set of rewriting rules. By using these terms, we obtain a natural and concise description of the conditional rewriting. Finally, starting from the representation of the conditional rewriting rules, we show how the rewriting calculus can be used to give a semantics to ELAN, a language based on the application of rewriting rules controlled by strategies.
No associations
LandOfFree
Rewriting Calculus: Foundations and Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rewriting Calculus: Foundations and Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rewriting Calculus: Foundations and Applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-114837