Preview

Труды Института системного программирования РАН

Расширенный поиск

Унификация программ

Аннотация

В данной работе в качестве эквивалентности программ рассматривается отношение логико-термальная эквивалентности, одно из наиболее слабых разрешимых отношений эквивалентности программ, аппроксимирующих отношение функциональной эквивалентности.

Об авторах

Т. А. Новикова
ИСП РАН
Россия


В. А. Захаров
ИСП РАН
Россия


Список литературы

1. Robinson J.A. A machine-oriented logic based on the resolution principle // Journal of the ACM. 1965 — v. 12, N 1. — p. 23-41.

2. Baxter L.D. An efficient unification algorithm // Technical Report CS-73-23, Dep. of Analysis and Comp. Sci., University of Waterloo, Ontario, Canada, 1973.

3. Paterson M.S., Wegman M.N. Linear unification // The Journal of Computer and System Science. — 1978. — v. 16, N 2 — p. 158-167.

4. Martelli A., Montanari U. An efficient unification algorithm //ACM Transactions on Program, Languages and Systems. — 1982. — v. 4, N 2 — p. 258-282.

5. Stickel E.M. A unification algorithm for associative-commutative functions // Journal of the association for Computing Machinary. — 1981. — v. 28, N 5 — p. 423-434.

6. Herold A., Sieckmann J. Unification in Abelean semigroups // Jornal of Automated Reasoning. — 1983. — p. 247-283.

7. Lincoln P., Christian J. Adventures in associative-commutative unification //Journal of Symbolic Computation. — 1989. — v.8. — p. 393 — 416.

8. Baader F., Snyder W. Unification theory // In J.A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning. — 2001. — v. 1 — p. 447-533.

9. Goldfarb W.D. The undecidability of the second-order unification problem // Theoretical Computer Science. — 1981. — v. 13, N 2. — p. 225-230.

10. Фаулер М. Рефакторинг. Улучшение существующего кода. — Символ-Плюс, 2008. — 432 c.

11. Roy C. K., Cordy J. R. A survey on software clone detection research // Technical report TR 2007-541, School of Computing, Queen’s University. — 2007. — v. 115.

12. Komondoor R., Horwitz S. Using slicing to identify duplication in source code // Proceedings of the 8th International Symposium on Static Analysis. — Springer-Verlag, 2001. — p. 40–56.

13. Иткин В.Э. Логико-термальная эквивалентность схем программ // Кибернетика. — 1972. — N 1. — с. 5-27.

14. Сабельфельд В.К. Полиномиальная оценка сложности распознавания логико-термальной эквивалентности // ДАН СССР. — 1979. — т. 249, N 4. — с. 793-796.

15. Захаров В.А., Новикова Т.А.. Применение алгебры подстановок для унификации программ. Труды Института системного программирования РАН, том 21, 2011 г. ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

16. Захаров В.А., Новикова Т.А.. Полиномиальный по времени алгоритм проверки логико-термальной эквивалентности программ. Труды Института системного программирования РАН, том 22, 2012 г. ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

17. Eder E. Properties of substitutions and unifications // Journal of Symbolic Computations. — v. 1. — 1985. — p. 31-46.

18. Palamidessi C. Algebraic properties of idempotent substitutions // Lecture Notes in Computer Science — v. 443 — 1990. — p. 386-399.

19. В.Е., Сабельфельд В.К. Теория схем программ. — М.:Наука, 1991. — 348 с.

20. Захаров В.А., Костылев Е.В. О сложности задачи антиунификации // Дискретная математика. — 2008. — т. 20, N 1. — с. 131-144.

21. Luckham D.C., Park D.M., Paterson M.S., On formalized computer programs // Journal of Computer and System Science — 1970. — v.4, N 3. — p. 220-249.

22. Котов В.Е., Сабельфельд В.К. Теория схем программ. — М.:Наука, 1991. — 348 с.


Рецензия

Для цитирования:


Новикова Т.А., Захаров В.А. Унификация программ. Труды Института системного программирования РАН. 2012;23.

For citation:


Novikova T.A., Zakharov V.A. Polynomial time algorithm for checking strong equivalence of program. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;23. (In Russ.)



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)