説明
A coterie under a ground set U consists of subsets (called quorums) of U such that any pair of quorums intersect with each other. Nondominated (ND) coteries are of particular interest, since they are optimal in some sense. By assigning a Boolean variable to each element in U, a family of subsets of U is represented by a Boolean function of these variables. The authors characterize the ND coteries as exactly those families which can be represented by positive, self-dual functions. In this Boolean framework, it is proved that any function representing an ND coterie can be decomposed into copies of the three-majority function, and this decomposition is representable as a binary tree. It is also shown that the class of ND coteries proposed by D. Agrawal and A. El Abbadi (1989) is related to a special case of the above binary decomposition, and that the composition proposed by M.L. Neilsen and M. Mizuno (1992) is closely related to the classical Ashenhurst decomposition of Boolean functions. A number of other results are also obtained. The compactness of the proofs of most of these results indicates the suitability of Boolean algebra for the analysis of coteries. >
収録刊行物
-
- IEEE Transactions on Parallel and Distributed Systems
-
IEEE Transactions on Parallel and Distributed Systems 4 (7), 779-794, 1993-07
Institute of Electrical and Electronics Engineers (IEEE)
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1363388844308958592
-
- NII論文ID
- 30020111024
-
- ISSN
- 10459219
-
- データソース種別
-
- Crossref
- CiNii Articles
- OpenAIRE
