Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-26T19:24:17.416Z Has data issue: false hasContentIssue false
  • English
  • Français

Generalisation of Dedekind's problem of the enumeration of coherent structures

Published online by Cambridge University Press:  14 November 2011

J. Ansell ,
A. Bendell  and
S. Humble
J. Ansell
Affiliation:
University of Keele
A. Bendell
Affiliation:
Dundee College of Technology
S. Humble
Affiliation:
Royal Military College of Science, Shrivenham
Get access Rights & Permissions [Opens in a new window]

Synopsis

In the context of reliability theory, two definitions are given for coherent functions of n variables, where both function and variables can take any of l possible levels. The enumeration problem for such functions is discussed and several recursive bounds are derived. In the case of l = 2 (the Dedekind problem) a recursive upper bound is derived which is better than the previous best explicit upper bound forn < 15, and also provides a systematic improvement on this bound for larger values of n.

Type
Research Article
Information
Proceedings of the Royal Society of Edinburgh Section A: Mathematics , Volume 89 , Issue 3-4 , 1981 , pp. 239 - 248
Copyright
Copyright © Royal Society of Edinburgh 1981

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1Alekseev, V. B.. On the number of k-valued monotonic functions. Soviet Math. Dokl. 14 (1973), 87–91.Google Scholar
2Barlow, R. E.. Multistate Network Reliability Theory. 11th European Meeting of Statisticians, Oslo, 1978, unpublished.Google Scholar
3Butler, D. A.. A complete importance ranking for components of binary coherent systems,with extensions to multi-state systems. Naval Res. Logist. Quart. 26 (1979), 565–578.CrossRefGoogle Scholar
4Birnbaum, Z. W., Esary, J. D. and Saunders, S. C.. Multi-component systems and structuresand their reliability. Technometrics 3 (1961), 55–77.CrossRefGoogle Scholar
5Church, R.. Enumeration by rank of the elements of the free distributive lattice with 7generators. Notices Amer. Math. Soc. 12 (1965), 724.Google Scholar
6Dedekind, R.. Uber Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler. Festschrift Technische Hochschule Braunschweig und Gesammelte Werke II (1897), 103. 148.Google Scholar
7Flegg, G.. Boolean Algebra and its Application (London: Blackie, 1964).Google Scholar
8Gilbert, E. N.. Lattice theoretic properties of frontal switching functions. J. Math. Phys. 33 (1954), 57–67.Google Scholar
9Hanisch, H., Hilton, P. J. and Hirsch, W. M.. Algebraic and combinational aspects of coherent structures. Trans. New York Acad. Sci. 31 (1969), 1024–1037.CrossRefGoogle Scholar
10Hansel, G.. Sur le nombres des fonctions booléenes monotones de n variables. C.R. Acad. Sci. Paris. Sér. A-B 262 (1966), A1088—A1090.Google Scholar
11Hatoyama, Y.. Reliability analysis of 3-state systems. IEEE Trans. Reliability R–28 (1979), 386–393.Google Scholar
12Kleitman, D.. On Dedekind's problem: the number of monotone Boolean functions. Proc. Amer. Math. Soc. 21 (1969), 677–682.Google Scholar
13Kleitman, D. and Markowsky, G.. On Dedekind's problem: the number of isotone Boolean functions II. Trans. Amer. Math. Soc. 213 (1975), 373–390.Google Scholar
14Korobkov, V. K.. Estimation of the number of monotonic functions of the algebra of logic and of the complexity of the algorithm for finding the resolvent set for an arbitrarymonotonic function of the algebra of logic. Soviet Math. Dokl. 4 (1963), 753–756.Google Scholar
15Kurshunov, A. D.. On Dedekind's problem of the number of monotone Boolean functions. Soviet Math. Dokl. 18 (1977), 442–445.Google Scholar
16Lomnicki, Z.. Some aspects of the statistical approach to reliability (with discussion). J. Roy. Statist. Soc. Ser. A 136 (1973), 395–419.CrossRefGoogle Scholar
17Moore, E. F. and Shannon, C. E.. Reliable circuits using less reliable relays. J. Franklin Inst. 262 (1956), 191–208.CrossRefGoogle Scholar
18Singh, B. and Proctor, C. L.. Reliability analysis of multistate devices networks. Proceedings Annual Reliability and Maintainability Symposium, 31—35 (New York:I.E.E.E., 1976).Google Scholar
19Virtanen, I.. On the concepts and derivation of reliability in stochastic systems withstates of reduced efficiency. Publ. Turku School Economics A4 (1977).Google Scholar
20Neumann, J. von. Probabilistic logics and the synthesis of reliable organisms from unreliable components. Automata Studies, pp. 43—98. Ann. Math. Studies 34 (Princeton, N.J.; Princeton Univ. Press, 1956).Google Scholar