ՀՀ ԳԱԱ Զեկույցներ =Reports NAS RA

О длинах тупиковых распознающих систем в классе двухэлементных подмножеств

Варданян, С. М. (2007) О длинах тупиковых распознающих систем в классе двухэлементных подмножеств. ՀՀ ԳԱԱ Զեկույցներ, 107 (1). pp. 37-43. ISSN 0321-1339

[img]PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
204Kb

Abstract

[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.

Item Type:Article
Additional Information:Երկէլեմենտ ենթաբազմությունների դասում փակուղային ճանաչող համակարգերի երկարության մասին / Ս. Մ. Վարդանյան։ On the Lengths of Deadlock Recognizing Systems in the Class of Subsets, Consisting of Two Elements / S. M. Vardanyan.
Uncontrolled Keywords:распознающие системы, пересечение множеств, тупиковость, максимальная мощность
Subjects:Q Science > QA Mathematics
ID Code:2572
Deposited By:NAS Reports
Deposited On:26 Mar 2012 15:57
Last Modified:13 Mar 2014 08:16

Repository Staff Only: item control page