Interval Term Rewriting System: Toward A Formal Model for Interval Computation

A.X. Carvalho, R.H.N. Santiago

Abstract


We present a term rewriting system for interval arithmetic (addition, subtraction and multiplication), toward a mathematical model for interval compu- tation. We start presenting a term rewriting system whose rules (directed equa- tions) perform binary floating-point arithmetic, which is based on IEEE-754 Stan- dard. Next, this primitive system is extended with rules for interval arithmetic. Finally, correctness and termination of our system are both discussed.

References


[1] F. Baader, T. Nipkow, “Term Rewriting and All That”, Cambridge University Press, 1998.

W.S. Brainerd, L. Landweber, “Theory of Computation”, John Wiley & Sons, New York, USA, 1974.

A.X. Carvalho, “Interval Term Rewriting System: Toward a formal model for interval computation”, Master thesis, UFRN-DIMAp, Natal, Brazil, 2005.

D. Goldberg, What every computer scientist should know about floating-point arithmetic, in “ACM Computing Surveys” pp. 5-48, 1991.

T. Hickey, Q. Ju, M. van Emden, Interval arithmetic: from principles to imple- mentation, in “Journal of the ACM” pp. 1038-1068, 2001.

S. Hollasch, IEEE standard 754 floating-point numbers, http://steve.hollasch.net/cgindex/coding/ieeefloat.html.

IEEE, “IEEE standard for binary floating-point arithmetic”, IEEE Computer Society Press, 1985.

R.B. Kearfott, Interval computations: Introduction, uses, and resources, in “Euromath Bulletin” pp. 95-112, 1996.

R. Kennaway, Complete term rewrite systems for decimal arithmetic and other total recursive functions, “Second International Workshop on Termination”, La Bresse, France, 1995.

C. Kirchner, H. Kirchner, “Rewriting Solving Proving”, LORIA, INRIA & CNRS, 2001.

H.R. Walters, H. Zantema, Rewrite systems for integer arithmetic, in RTA pp. 324–338, “Centrum voor Wiskunde en Informatica (CWI)”, 1995.




DOI: https://doi.org/10.5540/tema.2006.07.02.0249

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia