Generation methods of educational examples of programs with uncommon polynomial invariants

Authors

  • М.С. Львов Херсонский государственный университет, НИИ информационных технологий, Ukraine

DOI:

https://doi.org/10.15587/1729-4061.2010.2649

Keywords:

static analysis of programs, polynomial invariants of programs, automatic generation of examples

Abstract

The problem of generation of program examples with nontrivial polynomial invariants is considered. These examples are used in mathematical system of educational purpose “Static Analysis Systems”. The two methods are proposed: the method of algebraic dependencies and the method of L-invariants.

Author Biography

М.С. Львов, Херсонский государственный университет, НИИ информационных технологий

Кандидат физико-математических наук, доцент,
Директор НИИ информационных технологий

References

  1. R. W. Floyd. Assigning Meanings to Programs. In Proc/ Symposia in Applied Mathematics 19, pp 19-37, 1967.
  2. C. A. R. Hoare. An Axiomatic Basis for Computer Programming. Comm. ACM, 12, 1969.
  3. A.A. Letichevskiy. About one approach to program analysis // Cybernetics. - 1979.-№ 6.-с.1-8.
  4. A.B. Godlevskiy, Y.V. Kapitonova, S.SL. Krivoy, A.A. Letichevskiy. Iterative methods of program analysis // Cybernetics. – 1989. - №2, P.9-19.
  5. A.Letichevsky, M.Lvov. Discovery of invariant Equalities in Programs over Data fields. Applicable Algebra in Engineering, Communication and Computing. – 1993. – №4. – pp. 21-29.
  6. Markus Mller-Olm, Helmut Seidl: Precise interprocedural analysis through linear algebra. POPL 2004: 330-341.
  7. Markus Mller-Olm, Helmut Seidl: Computing polynomial program invariants. Inf. Process. Lett. 91(5): 233-244 (2004).
  8. Sriram Sankaranarayanan, Henny Sipma, Zohar Manna: Non-linear loop invariant generation using Grоbner bases. POPL 2004: 318-329.
  9. Michael Caplain: Finding Invariant Assertions for Proving Programs. In Proceedings of the international Conference on Reliable Software (Los Angeles, California, April 21 - 23, 1975): 165-171.
  10. Enric Rodriguez-Carbonell, Deepak Kapur: Automatic generation of polynomial loop invariants: algebraic foundations. ISSAC 2004: 266-273.
  11. Enric Rodriguez-Carbonell, Deepak Kapur: Automatic generation of polynomial invariants of bounded degree using abstract interpretation. Sci. Comput. Program. 64(1): 54-75 (2007).
  12. Laura Ildiko Kovacs, Tudor Jebelean: An Algorithm for Automated Generation of Invariants for Loops with Conditionals. SYNASC 2005: 245-249.

Published

2010-04-06

How to Cite

Львов, М. (2010). Generation methods of educational examples of programs with uncommon polynomial invariants. Eastern-European Journal of Enterprise Technologies, 2(4(44), 28–31. https://doi.org/10.15587/1729-4061.2010.2649

Issue

Section

Mathematics and Cybernetics - applied aspects