University of Illinois Urbana-Champaign
On the Connection Assignment Problem of Diagnosable Systems
Preparata, f.p.; metze, gernot; chien, r.t..
https://hdl.handle.net/2142/74464 Copy
Description
- Preparata, F.P.
- Metze, Gernot
- Chien, R.T.
- Automatic diagnosis
- Digital systems
- Connection assignment
- Joint Services Electronics Program / DA 28 043 AMC 00073(E)
- National Science Foundation / GK-690 and GK-36
Owning Collections
Report - coordinated science laboratory primary, manage files, edit collection membership, edit metadata, edit properties.
I don't have an Illinois NetID
Academia.edu no longer supports Internet Explorer.
To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .
Enter the email address you signed up with and we'll email you a reset link.
- We're Hiring!
- Help Center
On the Connection Assignment Problem of Diagnosable Systems
Related Papers
IFAC Proceedings Volumes
Philippe Dague
MELVIN BREUER
2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP)
Volodymyr Lytvynenko
Franc Novak
Information Processing Letters
Laszlo Liptak
IEEE Transactions on Computers
Israel Koren
Theoretical Computer Science
Krzysztof Diks , Andrzej Pelc
Mario Dal Cin
Andrzej Pelc
RELATED PAPERS
Clinical Cardiology
Jose Krieger
Hayula: Indonesian Journal of Multidisciplinary Islamic Studies
Uki Masduki
SSRN Electronic Journal
Filippo Natoli
International Journal of Network Management
sevgi sevsay
Santhi Wicks
Revista Campo-Território
GABRIEL LEITE DOMINGUES
emanuela ricotti
IJAR - Indian Journal of Applied Research
Singapore medical journal
Harsh Kandpal
Communications in agricultural and applied biological sciences
Olaf Strauch
Wireless Communications and Mobile Computing
Huyền Trang
Khalid Chakir
Journal of Educational Computing Research
Nuevo itinerario
Maria Angelica Fierro
Irina Koleva
Jean-Claude Margueron
ACTA SCIENTIFIC MICROBIOLOGY
NIshith Pal
International Journal of Molecular Sciences
Isao Nagaoka
Journal of Pesticide Science
Pushpendra Koli
RELATED TOPICS
- We're Hiring!
- Help Center
- Find new research papers in:
- Health Sciences
- Earth Sciences
- Cognitive Science
- Mathematics
- Computer Science
- Academia ©2024
The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
- Login or register account
INFONA - science communication portal
- advanced search
- conferences
- Collections
On the Connection Assignment Problem of Diagnosable Systems $("#expandableTitles").expandable();
- Contributors
Fields of science
- Bibliography
IEEE Transactions on Electronic Computers > 1967 > EC-16 > 6 > 848 - 854
Identifiers
User assignment, assignment remove confirmation, you're going to remove this assignment. are you sure.
Preparata, Franco P.
- Coordinated Science Laboratory and the Dept. of Elec. Engrg., University of Illinois, Urbana, Ill.
Metze, Gernot
Chien, robert t..
testing links Automatic diagnosis digital systems multiple faults
Additional information
- Read online
- Add to read later
- Add to collection
- Add to followed
Export to bibliography
- Terms of service
Accessibility options
- Report an error / abuse
Reporting an error / abuse
Sending the report failed.
Submitting the report failed. Please, try again. If the error persists, contact the administrator by writing to [email protected].
You can adjust the font size by pressing a combination of keys:
- CONTROL + + increase font size
- CONTROL + – decrease font
You can change the active elements on the page (buttons and links) by pressing a combination of keys:
- TAB go to the next element
- SHIFT + TAB go to the previous element
On the Connection Assignment Problem of Diagnosable Systems
FP Preparata ， G Metze ， RT Chien
展开
This paper treats the problem of automatic fault diagnosis for systems with multiple faults. The system is decomposed into n units u1, u2, . . . , un, where a unit is a well-identifiable portion of the system which cannot be further decomposed for the purpose of diagnosis. By means of a given arrangement of testing links (connection assignment) each unit of the system tests a subset of units, and a proper diagnosis can be arrived at for any diagnosable fault pattern. Methods for optimal assignments are given for instantaneous and sequential diagnosis procedures.
Automatic diagnosis digital systems multiple faults testing links
10.1109/PGEC.1967.264748
通过 文献互助 平台发起求助，成功后即可免费获取论文全文。
我们已与文献出版商建立了直接购买合作。
你可以通过身份认证进行实名认证，认证成功后本次下载的费用将由您所在的图书馆支付
您可以直接购买此文献，1~5分钟即可下载全文，部分资源由于网络原因可能需要更长时间，请您耐心等待哦~
百度学术集成海量学术资源，融合人工智能、深度学习、大数据分析等技术，为科研工作者提供全面快捷的学术服务。在这里我们保持学习的态度，不忘初心，砥砺前行。 了解更多>>
©2024 Baidu 百度学术声明 使用百度前必读
Stack Exchange Network
Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Understanding a step in a proof on diagnosability of graphs
I am currently writing a paper about diagnosability of graphs. For this, I am looking into a paper published in 1967 by Preparata, Metze and Chien called " On The Connection Assignment Problem of Diagnosable Systems ".
I am currently working through the proof of Theorem 5 within this paper and there is one step that I just can't understand. In the link above, this step happens right at the top of page 22 with the sentence:
The above stated condition (1) can be met if the number $n$ of units cannot be partitioned in less than $s$ sequences of the given maximum length.
Why is this true?
- graph-theory
- 2 $\begingroup$ It would be helpful if you could include some of the relevant definitions and statements in your question, to save people having to look through the whole of the article that you are referring to $\endgroup$ – Yemon Choi Sep 12, 2020 at 17:04
- $\begingroup$ You're definitely right about that, but the definitions come from an algorithm further up in the paper, so it is very hard to summarize all of those in just one post. $\endgroup$ – Sara Sep 12, 2020 at 17:32
- $\begingroup$ Hmm, is diagnosability of graphs related to the graph isomorphism disease ? (I thought for sure it was a typo for 'diagonalisable', but it appears not!) $\endgroup$ – LSpice Sep 14, 2020 at 13:57
I think I just solved it myself, so I'm just gonna put the answer here:
I ended up reshuffling the proof and using two properties. One is equation (3) from the same proof. The other property is $$s \ r_{max} \geq n,$$
which is true because we have split $n$ into $s$ segments of maximum length $r_{max}$ . Then we can combine the two properties to get (1).
Your Answer
Sign up or log in, post as a guest.
Required, but never shown
By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .
Not the answer you're looking for? Browse other questions tagged graph-theory or ask your own question .
- Featured on Meta
- Testing a new version of Stack Overflow Jobs
- What deliverables would you like to see out of a working group?
Characterization of Diagnosabilities on the Bounded PMC Model
Ieee account.
- Change Username/Password
- Update Address
Purchase Details
- Payment Options
- Order History
- View Purchased Documents
Profile Information
- Communications Preferences
- Profession and Education
- Technical Interests
- US & Canada: +1 800 678 4333
- Worldwide: +1 732 981 0060
- Contact & Support
- About IEEE Xplore
- Accessibility
- Terms of Use
- Nondiscrimination Policy
- Privacy & Opting Out of Cookies
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.
On the Connection Assignment Problem of Diagnosable Systems (Q29541433)
Identifiers, wikipedia (0 entries), wikibooks (0 entries), wikinews (0 entries), wikiquote (0 entries), wikisource (0 entries), wikiversity (0 entries), wikivoyage (0 entries), wiktionary (0 entries), multilingual sites (0 entries).
Navigation menu
IMAGES
VIDEO
COMMENTS
Abstract: This paper treats the problem of automatic fault diagnosis for systems with multiple faults. The system is decomposed into n units u 1, u 2, . . . , u n, where a unit is a well-identifiable portion of the system which cannot be further decomposed for the purpose of diagnosis.By means of a given arrangement of testing links (connection assignment) each unit of the system tests a ...
This paper treats the problem of automatic fault diagnosis for systems with multiple faults by means of a given arrangement of testing links (connection assignment), and a proper diagnosis can be arrived at for any diagnosable fault pattern. This paper treats the problem of automatic fault diagnosis for systems with multiple faults. The system is decomposed into n units u 1 , u 2 , . . . , u n ...
On the Connection Assignment Problem of Diagnosable Systems Author(s) Preparata, F.P. Metze, Gernot; Chien, R.T. Issue Date 1966-10 Keyword(s) Automatic diagnosis; Digital systems; Connection assignment; Publisher Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Series/Report Name or Number Coordinated Science ...
(DOI: 10.1109/PGEC.1967.264748) This paper treats the problem of automatic fault diagnosis for systems with multiple faults. The system is decomposed into n units u 1 , u 2 , . . . , u n , where a unit is a well-identifiable portion of the system which cannot be further decomposed for the purpose of diagnosis. By means of a given arrangement of testing links (connection assignment) each unit ...
Topics: Assignment problem Related papers: Characterization of Connection Assignment of Diagnosable Systems A comparison connection assignment for diagnosis of multiprocessor systems An 0(n 2.5 ) Fault Identification Algorithm for Diagnosable Systems On self-diagnosable multiprocessor systems: diagnosis by the comparison approach
EC-16, NO. 6, DECEMBER 1967 On the Connection Assignment Problem of Diagnosable Systems FRANCO P. PREPARATA, MEMBER, IEEE, GERNOT METZE, MEMBER, TEEE AND ROBERT T. CHIEN, MEMBER, IEEE Abstract-This paper treats the problem of automatic fault diag- ing several hundred active components. While being nosis for systems with multiple faults.
The system is decomposed into n units u 1, u 2, . . . , u n, where a unit is a well-identifiable portion of the system which cannot be further decomposed for the purpose of diagnosis. By means of a given arrangement of testing links (connection assignment) each unit of the system tests a subset of units, and a proper diagnosis can be arrived at ...
Characterization of Connection Assignment of Diagnosable Systems Abstract: Preparata, Metze, and Chien [1] gave necessary conditions for identification of all faulty units in a system S capable of automatic fault diagnosis. We show that these conditions are sufficient if in S no two units test each other. Necessary and sufficient conditions are ...
Connection Assignments for Probabilistically Diagnosable Systems This correspondence is concerned with probabilistic fault diagnosis for digital systems. A graph-theoretic model of a diagnosable system introduced by Preparata et al.[3] is considered in which a system is made up of a number of units with the ...
On the Connection Assignment Problem of Diagnosable Systems. This paper treats the problem of automatic fault diagnosis for systems with multiple faults. The system is decomposed into n units u1, u2, . . . , un, where a unit is a well-identifiable portion of the system which cannot be further decomposed for the purpose of diagnosis. By means of ...
The necessary and sufficient conditions are obtained for the existence of testing links (a connection) to form probabilistically t-diagnosable systems with and without repair. This correspondence is concerned with probabilistic fault diagnosis for digital systems. A graph-theoretic model of a diagnosable system introduced by Preparata et al.[3] is considered in which a system is made up of a ...
This correspondence is concerned with probabilistic fault diagnosis for digital systems. A graph-theoretic model of a diagnosable system introduced by Preparata et al.[3] is considered in which a ...
Characterization of connection assignment of diagnosable systems. IEEE Trans. Comput., C-23 (1974), pp. 86-88. View in Scopus Google Scholar [9] F. Harary. ... On the connection assignment problem of diagnosable systems. IEEE Trans. Comput., EC-16 (1967), pp. 848-854. View in Scopus Google Scholar [15]
Preparata, Metze and Chien [F.P. Preparata, G. Metze, R.T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Comput. EC 16 (12) (1967) 848-854] introduced a graph theoretical model for system-level diagnosis, in which processors perform tests on one another via links in the system.
I am currently writing a paper about diagnosability of graphs. For this, I am looking into a paper published in 1967 by Preparata, Metze and Chien called "On The Connection Assignment Problem of Diagnosable Systems".I am currently working through the proof of Theorem 5 within this paper and there is one step that I just can't understand.
In this paper, we propose a new digragh model for system level fault diagnosis, which is called the $(f_1,f_{2})$ -bounded Preparata-Metze-Chien (PMC) ... This novel testing model compromisingly generalizes PMC model (Preparata, F.P., Metze, G. and Chien R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Tran ...
It is shown that necessary conditions for identification of all faulty units in a system S capable of automatic fault diagnosis are sufficient if in S no two units test each other and for the general case when no such restriction is placed on S. Preparata, Metze, and Chien [1] gave necessary conditions for identification of all faulty units in a system S capable of automatic fault diagnosis ...
A graph-theoretic model of a diagnosable system introduced by Preparata et al.[3] is considered in which a system is made up of a number of units with the probability of failure. The necessary and sufficient conditions are obtained for the existence of testing links (a connection) to form probabilistically t-diagnosable systems with and without ...
EC-16 (1967), pp. 848-854] composed of n units is said to be t / ( t + 1) diagnosable [A. D. Friedman, A new measure of digital system diagnosis, in Dig. 1975 Int. Symp. Fault-Tolerant Comput., 1975, pp. 167-170] if, given a syndrome (complete collection of test results), the set of faulty units can be isolated to within a set of at most t ...
On the Connection Assignment Problem of Diagnosable Systems. scientific article (publication date: December 1967) Statements. instance of. scholarly article. 0 references. title. On the Connection Assignment Problem of Diagnosable Systems (English) 1 reference. stated in. DOI.org query endpoint. reference URL.
TLDR. An algorithm for identifying the set of faulty units in a tp-self-implicating system is given, which is linear in the number of tests in the system, rendering it more efficient than the most efficient known algorithm for the general class of t p-diagnosable systems. Expand. 37. Save. Diagnosability and diagnosis of algorithm-based fault ...