Mizar Analysis of Algorithms: Algorithms over Integers

Grzegorz Bancerek

Formalized Mathematics (2008)

  • Volume: 16, Issue: 2, page 177-194
  • ISSN: 1426-2630

Abstract

top
This paper is a continuation of [5] and concerns if-while algebras over integers. In these algebras the only elementary instructions are assignment instructions. The instruction assigns to a (program) variable a value which is calculated for the current state according to some arithmetic expression. The expression may include variables, constants, and a limited number of arithmetic operations. States are functions from a given set of locations into integers. A variable is a function from the states into the locations and an expression is a function from the states into integers. Additional conditions (computability) limit the set of variables and expressions and, simultaneously, allow to write algorithms in a natural way (and to prove their correctness).As examples the proofs of full correctness of two Euclid algorithms (with modulo operation and subtraction) and algorithm of exponentiation by squaring are given.MML identifier: AOFA I00, version: 7.8.10 4.100.1011

How to cite

top

Grzegorz Bancerek. "Mizar Analysis of Algorithms: Algorithms over Integers." Formalized Mathematics 16.2 (2008): 177-194. <http://eudml.org/doc/266774>.

@article{GrzegorzBancerek2008,
abstract = {This paper is a continuation of [5] and concerns if-while algebras over integers. In these algebras the only elementary instructions are assignment instructions. The instruction assigns to a (program) variable a value which is calculated for the current state according to some arithmetic expression. The expression may include variables, constants, and a limited number of arithmetic operations. States are functions from a given set of locations into integers. A variable is a function from the states into the locations and an expression is a function from the states into integers. Additional conditions (computability) limit the set of variables and expressions and, simultaneously, allow to write algorithms in a natural way (and to prove their correctness).As examples the proofs of full correctness of two Euclid algorithms (with modulo operation and subtraction) and algorithm of exponentiation by squaring are given.MML identifier: AOFA I00, version: 7.8.10 4.100.1011},
author = {Grzegorz Bancerek},
journal = {Formalized Mathematics},
language = {eng},
number = {2},
pages = {177-194},
title = {Mizar Analysis of Algorithms: Algorithms over Integers},
url = {http://eudml.org/doc/266774},
volume = {16},
year = {2008},
}

TY - JOUR
AU - Grzegorz Bancerek
TI - Mizar Analysis of Algorithms: Algorithms over Integers
JO - Formalized Mathematics
PY - 2008
VL - 16
IS - 2
SP - 177
EP - 194
AB - This paper is a continuation of [5] and concerns if-while algebras over integers. In these algebras the only elementary instructions are assignment instructions. The instruction assigns to a (program) variable a value which is calculated for the current state according to some arithmetic expression. The expression may include variables, constants, and a limited number of arithmetic operations. States are functions from a given set of locations into integers. A variable is a function from the states into the locations and an expression is a function from the states into integers. Additional conditions (computability) limit the set of variables and expressions and, simultaneously, allow to write algorithms in a natural way (and to prove their correctness).As examples the proofs of full correctness of two Euclid algorithms (with modulo operation and subtraction) and algorithm of exponentiation by squaring are given.MML identifier: AOFA I00, version: 7.8.10 4.100.1011
LA - eng
UR - http://eudml.org/doc/266774
ER -

References

top
  1. [1] Grzegorz Bancerek. Cardinal numbers. Formalized Mathematics, 1(2):377-382, 1990. 
  2. [2] Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990. 
  3. [3] Grzegorz Bancerek. Countable sets and Hessenberg's theorem. Formalized Mathematics, 2(1):65-69, 1991. 
  4. [4] Grzegorz Bancerek. Joining of decorated trees. Formalized Mathematics, 4(1):77-82, 1993. 
  5. [5] Grzegorz Bancerek. Mizar analysis of algorithms: Preliminaries. Formalized Mathematics, 15(3):87-110, 2007. 
  6. [6] Grzegorz Bancerek and Piotr Rudnicki. On defining functions on trees. Formalized Mathematics, 4(1):91-101, 1993. 
  7. [7] Grzegorz Bancerek and Piotr Rudnicki. Two programs for scm. Part I - preliminaries. Formalized Mathematics, 4(1):69-72, 1993. 
  8. [8] Grzegorz Bancerek and Andrzej Trybulec. Miscellaneous facts about functions. Formalized Mathematics, 5(4):485-492, 1996. 
  9. [9] Józef Białas. Infimum and supremum of the set of real numbers. Measure theory. Formalized Mathematics, 2(1):163-171, 1991. 
  10. [10] Ewa Burakowska. Subalgebras of the universal algebra. Lattices of subalgebras. Formalized Mathematics, 4(1):23-27, 1993. 
  11. [11] Czesław Byliński. Binary operations. Formalized Mathematics, 1(1):175-180, 1990. 
  12. [12] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990. 
  13. [13] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990. 
  14. [14] Czesław Byliński. The modification of a function by a function and the iteration of the composition of a function. Formalized Mathematics, 1(3):521-527, 1990. 
  15. [15] Czesław Byliński. Partial functions. Formalized Mathematics, 1(2):357-367, 1990. 
  16. [16] Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990. 
  17. [17] Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165-167, 1990. 
  18. [18] Noboru Endou, Katsumi Wasaki, and Yasunari Shidama. Definitions and basic properties of measurable functions. Formalized Mathematics, 9(3):495-500, 2001. 
  19. [19] Jarosław Kotowicz, Beata Madras, and Małgorzata Korolkiewicz. Basic notation of universal algebra. Formalized Mathematics, 3(2):251-253, 1992. 
  20. [20] Rafał Kwiatek. Factorial and Newton coefficients. Formalized Mathematics, 1(5):887-890, 1990. 
  21. [21] Rafał Kwiatek and Grzegorz Zwara. The divisibility of integers and integer relative primes. Formalized Mathematics, 1(5):829-832, 1990. 
  22. [22] Yatsuka Nakamura and Andrzej Trybulec. On a mathematical model of programs. Formalized Mathematics, 3(2):241-250, 1992. 
  23. [23] Beata Perkowska. Free universal algebra construction. Formalized Mathematics, 4(1):115-120, 1993. 
  24. [24] Konrad Raczkowski and Andrzej Nedzusiak. Real exponents and logarithms. Formalized Mathematics, 2(2):213-216, 1991. 
  25. [25] Piotr Rudnicki and Andrzej Trybulec. Abian's fixed point theorem. Formalized Mathematics, 6(3):335-338, 1997. 
  26. [26] Piotr Rudnicki and Andrzej Trybulec. Multivariate polynomials with arbitrary number of variables. Formalized Mathematics, 9(1):95-110, 2001. 
  27. [27] Andrzej Trybulec. Binary operations applied to functions. Formalized Mathematics, 1(2):329-334, 1990. 
  28. [28] Andrzej Trybulec. Function domains and Frænkel operator. Formalized Mathematics, 1(3):495-500, 1990. 
  29. [29] Michał J. Trybulec. Integers. Formalized Mathematics, 1(3):501-505, 1990. 
  30. [30] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990. 
  31. [31] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990. 
  32. [32] Edmund Woronowicz. Relations defined on sets. Formalized Mathematics, 1(1):181-186, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.