Երկէլեմենտ ենթաբազմությունների դասում փակուղային ճանաչող համակարգերի երկարության մասին / Ս. Մ. Վարդանյան։ On the Lengths of Deadlock Recognizing Systems in the Class of Subsets, Consisting of Two Elements / S. M. Vardanyan.

Պատ․ խմբ.՝ Վ. Հ․ Համբարձումյան (1944-1959) ; Մ․ Մ․ Ջրբաշյան (1960-1965) ; Ա․ Գ․ Նազարով (1966-1983) ; Պատ․ խմբ․ տեղակալ՝ Վ․ Հ․ Ղազարյան (1983-1986) ; Պատ․ խմբ․՝ Դ․ Մ․ Սեդրակյան (1987-1999) ; Գլխավոր խմբ․՝ Ս․ Ա․ Համբարձումյան (2000-2004) ; Վ․ Ս․ Զաքարյան (2005-2018) ; Ռ․ Մ․ Մարտիրոսյան (2018-)

распознающие системы ; пересечение множеств ; тупиковость ; максимальная мощность

37-43

[n]={1,2,n} վերջավոր բազմության ենթաբազմությունների համակարգը կոչվում է [n] -ը ճանաչող, եթե կամայական մեկ էլեմենտանոց բազմության {i},1≤i≤n, կարելի է ներկայացնել այդ համակարգի ինչ-որ բազմությունների հատման միջոցով: Դիտարկվում են այնպիսի համակարգեր, որոնք պարունակում են միայն երկէլեմենտ ենթաբազմություններ: Այդպիսի համակարգը կոչվում է մինիմալ, եթե գոյություն չունի ավելի փոքր հզորության ճանաչող համակարգ, և կոչվում է փակուղային, եթե այդ համակարգի ցանկացած խիստ ենթահամակարգ չի ճանաչում [n]-ը: Ապացուցվում է, որ (1) ներկայացված տեսքի ցանկացած փակուղային ճանաչող համակարգի հզորությունը ≤2(n-2);(2) կամայական j-ի համար n≤j≤2(n-2), գոյություն ունի նկարագրված տեսքի փակուղային ճանաչող համակարգ` j հզորության: A system S of subsets of the set [n]={1,2,…n} is said to be recognizing [n] , if every set {i},1≤i≤n can be represented as an intersection of sets belonging to S. Only subsets containing two elements are considered. A recognizing system S of such subsets is said to be minimal if there is no recognizing system having the power less than S; it is said to be deadlock if every its proper subsystem is not recognizing. It is proved that (1) every deadlock recognizing system of the mentioned kind has the power ≤2(n-2);(2) for every j,n≤j≤2(n-2) there exists a deadlock recognizing system of the mentioned kind having the power j.

Երևան

ՀՀ ԳԱԱ հրատ.

2007-03-15

Հոդված

Publication Details:

Journal or Publication Title:

Date of publication:

Volume:

Number:

ISSN:

Official URL:

Additional Information:

Title:

Other title:

Creator:

Contributor(s):

Subject:

Uncontrolled Keywords:

Coverage:

Abstract:

Place of publishing:

Publisher:

Date created:

Type:

Format:

Call number:

Digitization:

Location of original object: