{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T22:54:11Z","timestamp":1768776851328,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540220046","type":"print"},{"value":"9783540248408","type":"electronic"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24840-8_23","type":"book-chapter","created":{"date-parts":[[2010,8,8]],"date-time":"2010-08-08T18:58:39Z","timestamp":1281293919000},"page":"322-338","source":"Crossref","is-referenced-by-count":5,"title":["Average Case Self-Duality of Monotone Boolean Functions"],"prefix":"10.1007","author":[{"given":"Daya Ram","family":"Gaur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramesh","family":"Krishnamurti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"23_CR1","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1995.1157","volume":"123","author":"J. Bioch","year":"1995","unstructured":"Bioch, J., Ibaraki, T.: Complexity of identification and dualization of positive boolean functions. Information and Computation\u00a0123(1), 50\u201363 (1995)","journal-title":"Information and Computation"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0012-365X(94)00053-L","volume":"140","author":"J. Bioch","year":"1995","unstructured":"Bioch, J., Ibaraki, T.: Decomposition of positive self-dual functions. Discrete Mathematics\u00a0140, 23\u201346 (1995)","journal-title":"Discrete Mathematics"},{"issue":"9","key":"23_CR3","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1109\/71.466629","volume":"6","author":"J.C. Bioch","year":"1995","unstructured":"Bioch, J.C., Ibaraki, T.: Generating and approximating nondominated coteries. IEEE Transactions on parallel and distributed systems\u00a06(9), 905\u2013913 (1995)","journal-title":"IEEE Transactions on parallel and distributed systems"},{"key":"23_CR4","volume-title":"Random Graphs","author":"B. Bollobas","year":"1985","unstructured":"Bollobas, B.: Random Graphs. Academic Press, London (1985)"},{"issue":"1","key":"23_CR5","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1137\/S0097539793269089","volume":"26","author":"E. Boros","year":"1997","unstructured":"Boros, E., Hammer, P.L., Ibaraki, T., Kawakami, K.: Polynomial-time recognition of 2-monotonic positive boolean functions given by an oracle. SIAM Journal on Computing\u00a026(1), 93\u2013109 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/3-540-45841-7_10","volume-title":"STACS 2002","author":"E. Boros","year":"2002","unstructured":"Boros, E., Gurvich, V., Khachiyan, L., Makino, K.: On the complexity of generating maximal frequent and minimal infrequent sets. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 133\u2013141. Springer, Heidelberg (2002)"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0004-3702(87)90063-4","volume":"32","author":"J. Kleer de","year":"1987","unstructured":"de Kleer, J., Williams, B.C.: Diagnosing multiple faults. Artificial Intelligence\u00a032, 97\u2013130 (1987)","journal-title":"Artificial Intelligence"},{"issue":"1","key":"23_CR8","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/A:1007627028578","volume":"37","author":"C. Domingo","year":"1999","unstructured":"Domingo, C., Mishra, N., Pitt, L.: Efficient Read-Restricted Monotone CNF\/DNF Dualization by Learning with Membership Queries. Machine Learning\u00a037(1), 89\u2013110 (1999)","journal-title":"Machine Learning"},{"issue":"6","key":"23_CR9","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1137\/S0097539793250299","volume":"24","author":"T. Eiter","year":"1995","unstructured":"Eiter, T., Gottlob, G.: Identifying the minimum transversals of a hypergraph and related problems. Siam Journal of Computing\u00a024(6), 1278\u20131304 (1995)","journal-title":"Siam Journal of Computing"},{"key":"23_CR10","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/3-540-45757-7_53","volume-title":"Logics in Artificial Intelligence","author":"T. Eiter","year":"2002","unstructured":"Eiter, T., Gottlob, G.: Hypergraph Transversal Computation and Related Problems in Logic and AI. In: Flesca, S., Greco, S., Leone, N., Ianni, G. (eds.) JELIA 2002. LNCS (LNAI), vol.\u00a02424, pp. 549\u2013564. Springer, Heidelberg (2002)"},{"key":"23_CR11","unstructured":"Eiter, T., Makino, K.: On computing all abductive explanations. In: Proceeding 18th National Conference on Artificial Intelligence, AAAI 2002, pp. 62\u201367 (2002)"},{"key":"23_CR12","volume-title":"Introduction to Probability Theory and its Applications","author":"W. Feller","year":"1967","unstructured":"Feller, W.: Introduction to Probability Theory and its Applications, 3rd edn. John Wiley and Sons, Chichester (1967)","edition":"3"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Franco, J.: On the probabilistic performance of the algorithms for the satisfiability problem. Information Processing Letters, 103\u2013106 (1986)","DOI":"10.1016\/0020-0190(86)90051-7"},{"issue":"3","key":"23_CR14","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"M.L. Fredman","year":"1996","unstructured":"Fredman, M.L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms\u00a021(3), 618\u2013628 (1996)","journal-title":"Journal of Algorithms"},{"key":"23_CR15","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1145\/4221.4223","volume":"32","author":"H. Garcia-Molina","year":"1985","unstructured":"Garcia-Molina, H., Barbara, D.: How to assign votes in a distributed system. Journal of the ACM\u00a032, 841\u2013860 (1985)","journal-title":"Journal of the ACM"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Gaur, D., Krishnamurti, R.: Self-duality of bounded monotone boolean functions and related problems. In: The Eleventh Conference on Algorithmic Learning Theory. Lecture Notes in Computer Science (subseries LNAI), pp. 209\u2013223 (2000)","DOI":"10.1007\/3-540-40992-0_16"},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"Gunopulos, D., Khardon, R., Mannila, H., Toivonen, H.: Data mining, Hypergraph Transversals, and Machine Learning. In: Proc. Symposium on Principles of Database Systems, pp. 209\u2013216 (1997)","DOI":"10.1145\/263661.263684"},{"issue":"2","key":"23_CR18","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/0020-0190(82)90110-7","volume":"15","author":"A. Goldberg","year":"1982","unstructured":"Goldberg, A., Purdom, P., Brown, C.: Average time analysis for simplified davisputnam procedures. Information Processing Letters\u00a015(2), 72\u201375 (1982)","journal-title":"Information Processing Letters"},{"key":"23_CR19","unstructured":"Gurvich, V., Khachiyan, L.: Generating the irredundant conjunctive and disjunctive normal forms of monotone boolean functions. Technical Report LCSR-TR-251, Dept. of Computer Science, Rutgers Univ. (August 1995)"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Ibaraki, T., Kameda, T.: A boolean theory of coteries. IEEE Transactions on Parallel and Distributed Systems, 779\u2013794 (1993)","DOI":"10.1109\/71.238300"},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 14\u201322 (2002)","DOI":"10.1145\/509907.509912"},{"key":"23_CR22","unstructured":"Makino, K.: Studies on Positive and Horn Boolean Functions with Applications to Data Analysis. PhD thesis, Kyoto University (March 1997)"},{"issue":"2-3","key":"23_CR23","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0166-218X(02)00204-4","volume":"126","author":"K. Makino","year":"2003","unstructured":"Makino, K.: Efficient dualization of O(log n) term disjunctive normal forms. Discrete Applied Mathematics\u00a0126(2-3), 305\u2013312 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/3-540-58325-4_196","volume-title":"Algorithms and Computation","author":"K. Makino","year":"1994","unstructured":"Makino, K., Ibaraki, T.: The maximum latency and identification of positive boolean functions. In: Du, D.-Z., Zhang, X.-S. (eds.) ISAAC 1994. LNCS, vol.\u00a0834, pp. 324\u2013332. Springer, Heidelberg (1994)"},{"key":"23_CR25","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/0022-0000(86)90015-2","volume":"22","author":"H. Mannila","year":"1986","unstructured":"Mannila, H., R\u00e4ih\u00e4, K.J.: An application of armstrong relations. Journal of Computer and System Science\u00a022, 126\u2013141 (1986)","journal-title":"Journal of Computer and System Science"},{"key":"23_CR26","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1137\/0214067","volume":"14","author":"P.W. Purdom","year":"1985","unstructured":"Purdom, P.W., Brown, C.A.: The pure literal rule and polynomial average time. SIAM Journal on Computing\u00a014, 943\u2013953 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR27","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0004-3702(87)90062-2","volume":"32","author":"R. Reiter","year":"1987","unstructured":"Reiter, R.: A theory of diagnosis from first principles. Artificial Intelligence\u00a032, 57\u201395 (1987)","journal-title":"Artificial Intelligence"},{"key":"23_CR28","doi-asserted-by":"crossref","unstructured":"Wendt, P.D., Coyle, E.J., Gallagher Jr., N.C.: Stack filters. IEEE Transactions on Acoustics, Speech and Signal Processing 34(4), 898\u2013911","DOI":"10.1109\/TASSP.1986.1164871"}],"container-title":["Lecture Notes in Computer Science","Advances in Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24840-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T17:02:24Z","timestamp":1558285344000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24840-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540220046","9783540248408"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24840-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}