D:\sbornik\...\Article.DVI


Mathematical Problems of Computer Science 37, 35{38, 2012.

On M aximal Dead-end Recognizing Systems in the

Class of T wo-E lement Subsets Concer ning Oper ations

of I nter section and Complement

S e yr a n M. V a r d a n ya n

Institute for Informatics and Automation Problems of NAS of RA
e-mail: seyranv@ipia.sci.am

Abstract

The structure of dead-end n{recognizing systems having a maximal possible length
in the class of two-element subsets concerning the operations of intersection and com-
plement is investigated. The quantity of such systems is estimated.

Refer ences

[1 ] Ï. Ýðäåø, Äæ. Ñïåíñåð, Âåðîÿòíîñòíûå ìåòîäû â êîìáèíàòîðèêå. Ìîñêâà,
”Ìèð”, 1976.

[2 ] Ñ. Ì. Âàðäàíÿí, “Îá îäíîé çàäà÷å ðàñïîçíàâàíèÿ ìíîæåñòâ”, ÄÀÍ Àðì.
ÑÑÐ, òîì 72, ññ. 141- 143, 1981.

[3 ] Ñ. Ì. Âàðäàíÿí, “Î äëèíàõ òóïèêîâûõ ðàñïîçíàþùèõ ñèñòåì â êëàññå
äâóõýëåìåíòíûõ ïîäìíîæåñòâ”, ÄÍÀÍ ÐÀ, òîì 107, N 1, ññ. 37 - 43, 2007.

[4 ] S . M. V a r d a n ya n , \ R e c o g n iz ig s e t s ( s ys t e m s ) " P roceedings of International Confer-
ence Computer Science and Information Technologies CSIT05, p p .1 6 1 - 1 6 2 , Y e r e va n ,
A r m e n ia 2 0 0 5 .

[5 ] S . M. V a r d a n ya n , \ On t h e p o we r s o f d e a d -e n d r e c o g n iz in g s ys t e m s in t h e c la s s o f t wo -
e le m e n t s e t s c o n c e r n in g o p e r a t io n s o f in t e r s e c t io n a n d c o m p le m e n t " , M athematical
P roblems of Computer Sciences, vo l. 3 5 , p p . 1 0 4 { 1 0 8 , 2 0 1 1 .

[6 ] Ñ. Ì. Âàðäàíÿí, “Î ìèíèìàëüíîñòè íåêîòîðûõ ðàñïîçíàþùèõ ñèñòåì
â êëàññå äâóõýëåìåíòíûõ ïîäìíîæåñòâ îòíîñèòåëüíî îïåðàöèé
ïåðåñå÷åíèÿ è äîïîëíåíèÿ”, ÄÍÀÍ ÐÀ, òîì 112, N 1, ññ. 57 - 66, 2012.

[7 ] F. H a r a r y, Graph Theory, A d d is o n - W e s le y. R e a d in g MA 1 9 6 9 .

3 5



3 6 On Maximal Dead-end Recognizing Systems in the Class of Two-Element Subsets

гïÙ³Ý ¨ Éñ³óÙ³Ý ·áñÍáÕáõÃÛáõÝÝ»ñÇ Ýϳïٳٵ »ñÏï³ññ
»Ýóµ³½ÙáõÃÛáõÝÝ»ñÇ ¹³ëáõÙ ³é³í»É³·áõÛÝ »ñϳñáõÃÛáõÝ

áõÝ»óáÕ ×³Ý³ãáÕ ÷³ÏáõÕ³ÛÇÝ Ñ³Ù³Ï³ñ·»ñÇ Ù³ëÇÝ

ê. ì³ñ¹³ÝÛ³Ý

²Ù÷á÷áõÙ

²é³í»É³·áõÛÝ Ñݳñ³íáñ »ñϳñáõÃÛáõÝ áõÝ»óáÕ n-׳ݳãáÕ ÷³ÏáõÕ³ÛÇÝ Ñ³Ù³Ï³ñ·»ñÇ
ϳéáõóí³ÍùÁ ѻﳽáïíáõÙ ¿ »ñÏï³ññ »Ýóµ³½ÙáõÃÛáõÝÝ»ñÇ ¹³ëáõÙ Éñ³óÙ³Ý ¨
ѳïÙ³Ý ·áñÍáÕáõÃÛáõÝÝ»ñÇ Ýϳïٳٵ: ¶Ý³Ñ³ïíáõÙ ¿ ÝÙ³Ý ïÇåÇ Ñ³Ù³Ï³ñ·»ñÇ
ù³Ý³ÏÁ:

Î ðàñïîçíàþùèõ òóïèêîâûõ ñèñòåìàõ,
èìåþùèõ íàèáîëüøóþ âîçìîæíóþ äëèíó

â êëàññå äâóõýëåìåíòíûõ ïîäìíîæåñòâ îòíîñèòåëüíî
îïåðàöèé ïåðåñå÷åíèÿ è äîïîëíåíèÿ

Ñ. Âàðäàíÿí

Àííîòàöèÿ

Èññëåäóåòñÿ ñòðóêòóðà n-ðàñïîçíàþùèõ òóïèêîâûõ ñèñòåì, èìåþùèõ
íàèáîëüøóþ âîçìîæíóþ äëèíó â êëàññå äâóõýëåìåíòíûõ ïîäìíîæåñòâ
îòíîñèòåëüíî îïåðàöèé ïåðåñå÷åíèÿ è äîïîëíåíèÿ. Îïèñûâàþòñÿ
âñåâîçìîæíûå òèïû n-ðàñïîçíàþùèõ ìàêñèìàëüíûõ òóïèêîâûõ ñèñòåì è
äàåòñÿ îöåíêà êîëè÷åñòâà òàêèõ ñèñòåì.