Affiliations: IT Educational and Research Center, Yerevan State University, A. Manoogian 1, Yerevan, Armenia. hgrigorian@gmail.com | Institute for Informatics and Automation Problems, National Academy of Sciences of the Republic of Armenia, P. Sevak 1, Yerevan, Armenia. arsen.shoukourian@gmail.com
Note: [] Address for correspondence: IT Educational and Research Center, Yerevan State University, A. Manoogian 1, Yerevan, Armenia
Abstract: In this paper, the functional equivalence problem for processes, which is an important constituent of process optimization, is considered in object-oriented environments. Two basic cases are investigated: when the turn of operations execution is not essential for some objects while it is essential for the rest of them. In the first case, those objects are named commutative. Environments with both commutative and non-commutative objects are named partially commutative. It is shown, that the equivalence problem of processes in partially commutative environments that contain two or more commutative objects with more than one operation is unsolvable. The largest class of partially commutative environments is outlined where the equivalence problem is solvable (decidable). It is shown, that if there is only one object with two or more operations among commutative objects then the equivalence problem is solvable.
Keywords: object-oriented environment, environment model, model equation, process, equivalence of processes, multitape multidimensional automaton, partially commutative, regular expression
