D:\sbornik\...\article_eng.DVI Mathematical Problems of Computer Science 31, 130{141, 2008. On One Appr oach to Optimization of Recur sive Function Computations A r t a s h e s K . Gh a z a r ya n Institute for Informatics and Automation Problems of NAS of RA. E-mail: artashesg@gmail.com Abstract The goal of this work is the theoretical justi¯cation and the development of a new optimizer that synthesizes programs calculating multivariate recursive functions and systems of functions. The current version of the optimizer processes a wide category of multivariate systems of recursive functions using two algorithms { stack recursion optimization and combined total replacement optimization. The results of this work can be used in development of packages, calculating the systems of recursive functions, modeling discrete multivariate systems with complex interconnections, solving boundary-value and ¯eld-value problems, etc. Refer ences [1 ] Ìàðàíäæÿí Ã.Á, “Îá îäíîì ìåòîäå ñèíòåçà ïðîãðàìì ÷èñëîâûõ ôóíêöèé”, Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè è âû÷èñëèòåëüíîé òåõíèêè, XVI, 1986. [2 ] Ma r a n d jia n H ., General form recursive equations, CS L , p p . 5 0 1 -5 1 1 , 1 9 9 4 . [3 ] Ma n n a , Z., Theory of Computation. N Y , Mc Gr o w-H ill 1 9 7 8 . [4 ] B a r r o n D ., R ecursive methods in programming, Ge n e r a l E d it o r : S t a n le y Gill A s s o c ia t e E d it o r : J. J. Flo r e n t in , 1 9 6 9 . [5 ] A h o A .V ., H o p c r o ft J. E . a n d U lm a n J.D ., D ata Structures and Algoritms. A d d is o n - W e s le y, R e a d in g , Ma s s a c h u s e t t s . 1 9 8 3 . [6 ] B a r e n d r e g t , H . P ., The lambda calculus. Its syntax and semantics, N o r t h -H o lla n d , 1 9 8 4 . [7 ] Gh a z a r ya n A ., On one method of °exible numeration, P r o c e e d in g s o f t h e c o n fe r e n c e , CS IT, p . 1 5 , 1 9 9 7 . [8 ] K n a s t e r B . Une th¶eorµeme sur les fonctions d'ensembles. A n n a le s S o c . P o lo n a is e Ma t h ., 6 2 , p p . 1 3 3 { 1 3 4 , 1 9 2 7 . [9 ] R ic e H . G., Classes of recursively enumerable sets and their decision problems, Tr a n s . A m e r . Ma t h . S o c , p p . 3 5 8 { 3 6 6 , 1 9 7 4 . [1 0 ] K le e n e , S . C., Introduction to M etamathematics. N e w Y o r k - To r o n t o , D . V a n N o s t r a n d Co ., In c ., 1 9 5 2 . [1 1 ] Õàëàòÿí, È. Ã., Ïàêåò ïðèêëàäíûõ ïðîãðàìì - àâòîìàòè÷åñêèé ïðîãðàììíûé ñèíòåç. Òåçèñû äîêëàäîâ Òðåòüåé Ðåñïóáëèêàíñêîé êîíôåðåíöèè àñïèðàíòîâ Àðìÿíñêîé ÑÑÐ, ×àñòü 2, Åðåâàí, ññ. 16 -17, 1989. 1 3 0 A. Ghazaryan 1 3 1 [1 2 ] A m d a h l G. M., Validity of the single-processor approach to achieving large scale com- puting capabilities. In A FIP S Co n fe r e n c e P r o c e e d in g s vo l. 3 0 ( A t la n t ic Cit y, N .J., A p r . 1 8 -2 0 ) . A FIP S P r e s s , R e s t o n , V a ., p p . 4 8 3 -4 8 5 , 1 9 6 7 . è»ÏáõñëÇí ýáõÝÏódzݻñÇ Ñ³ßíÙ³Ý ûåïÇٳɳóÙ³Ý ÙÇ »Õ³Ý³ÏÇ í»ñ³µ»ñÛ³É ². Ô³½³ñÛ³Ý ²Ù÷á÷áõÙ ²Ûë ³ß˳ï³ÝùÇ Ýå³ï³ÏÝ ¿ Ýáñ ûåïÇٳɳóÙ³Ý Ùß³ÏáõÙÝ áõ ï»ë³Ï³Ýáñ»Ý ³ñ¹³ñ³óí³Í ÉÇÝ»ÉÁ, áñÁ ëÇÝû½áõÙ ¿ µ³½Ù³ã³÷ é»ÏáõñëÇí ýáõÝÏódzݻñ ¨ ýáõÝÏódzݻñÇ Ñ³Ù³Ï³ñ·»ñ ѳßíáÕ Íñ³·ñ»ñ: úåïÇٳɳñÇÝ Ý»ñϳ۳óíáÕ ï³ñµ»ñ³ÏÁ Ùß³ÏíáõÙ ¿ é»ÏáõñëÇí ýáõÝÏódzݻñÇ µ³½Ù³ã³÷ ѳٳϳñ·»ñÇ É³ÛÝ ¹³ëǪ û·ï³·áñÍ»Éáí »ñÏáõ ³É·áñÇÃÙ. ëï»Ï³ÛÇÝ é»ÏáõñëdzÛÇ ûåïÇٳɳóáõÙ ¨ ÉñÇí ÷á˳ñÇÝÙ³Ý ³É·áñÇÃÙÇ Ùdzíáñí³Í ûåïÇٳɳóáõÙ: ²Ûë ³ß˳ï³ÝùÇ ³ñ¹ÛáõÝùÝ»ñÁ ϳñ»ÉÇ ¿ û·ï³·áñÍ»É ³ÛÝ Íñ³·ñ³ß³ñ»ñÇ Ùß³ÏÙ³Ý Ù»ç, áñáÝù ѳßíáõÙ »Ý é»ÏáõñëÇí ýáõÝÏódzݻñÇ Ñ³Ù³Ï³ñ·»ñ, ÙṻɳíáñáõÙ »Ý µ³ñ¹ ÷áËϳå³ÏóáõÃÛáõÝÝ»ñáí ÁÝ¹Ñ³ï µ³½Ù³ã³÷ ѳٳϳñ·áñ, ÉáõÍáõÙ »Ý »½ñ³ÛÇÝ ¨ ¹³ßï³ÛÇÝ ËݹÇñÝ»ñ ¨ ³ÛÉÝ: