Mizar Analysis of Algorithms: Algorithms over Integers
Grzegorz Bancerek
Formalized Mathematics, Tome 16 (2008), p. 177-194 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:266774 
@article{bwmeta1.element.doi-10_2478_v10037-008-0024-0,
     author = {Grzegorz Bancerek},
     title = {Mizar Analysis of Algorithms: Algorithms over Integers},
     journal = {Formalized Mathematics},
     volume = {16},
     year = {2008},
     pages = {177-194},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_v10037-008-0024-0}
}

Grzegorz Bancerek. Mizar Analysis of Algorithms: Algorithms over Integers. Formalized Mathematics, Tome 16 (2008) pp. 177-194. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_v10037-008-0024-0/

[1] Grzegorz Bancerek. Cardinal numbers. Formalized Mathematics, 1(2):377-382, 1990.

[2] Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990.

[3] Grzegorz Bancerek. Countable sets and Hessenberg's theorem. Formalized Mathematics, 2(1):65-69, 1991.

[4] Grzegorz Bancerek. Joining of decorated trees. Formalized Mathematics, 4(1):77-82, 1993.

[5] Grzegorz Bancerek. Mizar analysis of algorithms: Preliminaries. Formalized Mathematics, 15(3):87-110, 2007.

[6] Grzegorz Bancerek and Piotr Rudnicki. On defining functions on trees. Formalized Mathematics, 4(1):91-101, 1993.

[7] Grzegorz Bancerek and Piotr Rudnicki. Two programs for scm. Part I - preliminaries. Formalized Mathematics, 4(1):69-72, 1993.

[8] Grzegorz Bancerek and Andrzej Trybulec. Miscellaneous facts about functions. Formalized Mathematics, 5(4):485-492, 1996.

[9] Józef Białas. Infimum and supremum of the set of real numbers. Measure theory. Formalized Mathematics, 2(1):163-171, 1991.

[10] Ewa Burakowska. Subalgebras of the universal algebra. Lattices of subalgebras. Formalized Mathematics, 4(1):23-27, 1993.

[11] Czesław Byliński. Binary operations. Formalized Mathematics, 1(1):175-180, 1990.

[12] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990.

[13] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990.

[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] Czesław Byliński. Partial functions. Formalized Mathematics, 1(2):357-367, 1990.

[16] Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990.

[17] Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165-167, 1990.

[18] Noboru Endou, Katsumi Wasaki, and Yasunari Shidama. Definitions and basic properties of measurable functions. Formalized Mathematics, 9(3):495-500, 2001.

[19] Jarosław Kotowicz, Beata Madras, and Małgorzata Korolkiewicz. Basic notation of universal algebra. Formalized Mathematics, 3(2):251-253, 1992.

[20] Rafał Kwiatek. Factorial and Newton coefficients. Formalized Mathematics, 1(5):887-890, 1990.

[21] Rafał Kwiatek and Grzegorz Zwara. The divisibility of integers and integer relative primes. Formalized Mathematics, 1(5):829-832, 1990.

[22] Yatsuka Nakamura and Andrzej Trybulec. On a mathematical model of programs. Formalized Mathematics, 3(2):241-250, 1992.

[23] Beata Perkowska. Free universal algebra construction. Formalized Mathematics, 4(1):115-120, 1993.

[24] Konrad Raczkowski and Andrzej Nedzusiak. Real exponents and logarithms. Formalized Mathematics, 2(2):213-216, 1991.

[25] Piotr Rudnicki and Andrzej Trybulec. Abian's fixed point theorem. Formalized Mathematics, 6(3):335-338, 1997.

[26] Piotr Rudnicki and Andrzej Trybulec. Multivariate polynomials with arbitrary number of variables. Formalized Mathematics, 9(1):95-110, 2001.

[27] Andrzej Trybulec. Binary operations applied to functions. Formalized Mathematics, 1(2):329-334, 1990.

[28] Andrzej Trybulec. Function domains and Frænkel operator. Formalized Mathematics, 1(3):495-500, 1990.

[29] Michał J. Trybulec. Integers. Formalized Mathematics, 1(3):501-505, 1990.

[30] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990.

[31] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990.

[32] Edmund Woronowicz. Relations defined on sets. Formalized Mathematics, 1(1):181-186, 1990.