vahan_margaryan.DVI


Mathematical Problems of Computer Science 26, 2006, 21{27.

On Restr iction Optimal Fixpoints

V a h a n K . Ma r g a r ya n

Department of Informatics and Applied Mathematics
of Yerevan State University

e-mail vahan80a@netsys.am

Abstract

Optimal ¯xpoints extract maximum consistent information from recursive pro-
grams. However, optimal ¯xpoints, although they always exist for a recursive operator,
aren't necessarily computable.

We have introduced a modi¯ed notion of the optimal ¯xpoint, where the recursive
operators are restricted to computable inputs. Existence results for and properties of
this ¯xpoint are summarized in the article.

Refer ences

[1 ] Z. Ma n n a , A . S h a m ir . Th e o p t im a l a p p r o a c h t o r e c u r s ive p r o g r a m s . Communications of
the ACM 1 1 :8 2 4 -8 3 1

[2 ] V . Ma r g a r ya n . On c e r t a in p r o p e r t ie s o f c o m p u t a b le o p t im a l ¯ xp o in t s . P roceedings of
CSIT-2003,

[3 ] A . P a t t e r s o n . Im p lic it P r o g r a m m in g a n d Th e L o g ic o f Co n s t r u c t ib le D u a lit y, P h.D .
Thesis, University of Illinois at Urbana-Champaign, 1 9 9 8

ê³Ñٳݳ÷³ÏÙ³Ý ûåïÇÙ³É ³Ýß³ñÅ Ï»ï»ñÇ Ù³ëÇÝ

ì. سñ·³ñÛ³Ý

²Ù÷á÷áõÙ

úåïÇÙ³É ³Ýß³ñÅ Ï»ï»ñÁ ³é³í»É³·áõÛÝ ÇÝýáñÙ³óÇ³Ý »Ý å³ñáõݳÏáõÙ é»ÏáõñëÇí
Íñ³·ñÇ Ù³ëÇÝ: ê³Ï³ÛÝ ¹ñ³Ýù ϳñáÕ »Ý ÉÇÝ»É áã ѳßí³ñÏ»ÉÇ: Ø»Ýù Ý»ñÙáõÍ»É »Ýù
ûåïÇÙ³ÉáõÃÛ³Ý ÷á÷áËí³Í ·³Õ³÷³ñ, áñÇ ¹»åùáõÙ ¹Çï³ñÏíáõÙ ¿ ÙdzÛÝ Ñ³ßí³ñÏ»ÉÇ
ýáõÝÏódzݻñÇ íñ³ ûå»ñ³ïáñÇ ·áñÍáÕáõÃÛáõÝÁ: Ðá¹í³ÍáõÙ Ý»ñϳ۳óí³Í »Ý ³ÛÝ
³Ýß³ñÅ Ï»ïÇ ·áÛáõÃÛ³Ý »í ѳïÏáõÃÛáõÝÝ»ñÇ í»ñ³µ»ñÛ³É ³ñ¹ÛáõÝùÝ»ñÇ ³Ù÷á÷áõÙ:

2 1