PAIS Lab Seminar: Fast algorithms for program equivalence checking using semigroup-semantics models
The talk presents the results obtained in the study of the equivalence problem for the models of sequential and recursive programs with the semantics defined on the basis of semigroups.
The equivalence of programs in such models is usually a sufficient condition for the functional equivalence of real programs.
Key findings of the research are (1) the description of the algorithms for checking equivalence of polynomial time on the size of the programs, and (2) the proof of the polynomial solvability of the problem of equivalence of programs in some of these models.
Date
11 January
2015