Equivalence of Processes in Partially Commutative Object-Oriented Environments

• Autorzy: Grigoryan H. , Shoukourian A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

object-oriented environment; environment model; model equation; process; equivalence of processes; multitape multidimensional automaton; partially commutative; regular expressions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 105, nr 4
• Strony: 417--434
• Opis fizyczny: Bibliogr. 11 poz., wykr.

Twórcy

autor

Grigoryan H.

autor

Shoukourian A.

• IT Educational and Research Center, Yerevan State University, A. Manoogian 1, Yerevan, Armenia,

Bibliografia

• [1] Baeten, J.: A brief history of process algebra, Theoretical Computer Science, 335(2-3), 2005, 131-146.
• [2] Bergstra, J., Ponse, A., Smolka, S., Eds.: Handbook of Process Algebra, Elsevier Science, 2001.
• [3] Bloom, B.: When is Partial Trace Equivalence Adequate?, Formal Aspects of Computing, 6(3), 1994, 317-338.
• [4] Godlevskii, A., Letichevskii, A., Shukuryan, S.: Reducibility of program-scheme functional equivalence on a nondegenerate basis of rank unity to the equivalence of automata with multidimensional tapes, Cybernetics and Systems Analysis, 16(6), 1980, 793-799.
• [5] Grigorian, H., Shoukourian, S.: The Equivalence Problem of Multidimensional Multitape Automata, Journal of Computer and System Sciences, 74(7), 2008, 1131-1138.
• [6] Grigoryan, H.: Equivalence of Processes in an Object-Oriented Environment, Reports of the National Academy of Sciences of Armenia, 108(1), 2008, 50-59.
• [7] Magnani, L., Nersessian, N., Thagard, P.: Model-Based Reasoning in Scientific Discovery, Springer, 1999.
• [8] Raulefs, P.: The Virtual Factory, IFIP World Computer Congress, volume 2, 1994, pp.18-30.
• [9] Shoukourian, A.: Equivalence of regular expressions over a partially commutative alphabet, Cybernetics and Systems Analysis, 45(3), 2009, 387-396.
• [10] Tuzov, V.: Decision problems for graph schemata with commutable operators. Part II, Cybernetics and Systems Analysis, 7(5), 1971, 778-789.
• [11] Vargas-Villamil, F., Rivera, D., Kempf, K.: A Hierarchical Approach to Production Control of Reentrant Semiconductor Manufacturing Lines, IEEE Transactions on Control Systems Technology, 11(4), 2003, 578-587.