{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T02:10:41Z","timestamp":1775614241472,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540441908","type":"print"},{"value":"9783540457572","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45757-7_53","type":"book-chapter","created":{"date-parts":[[2007,10,20]],"date-time":"2007-10-20T13:50:39Z","timestamp":1192888239000},"page":"549-564","source":"Crossref","is-referenced-by-count":52,"title":["Hypergraph Transversal Computation and Related Problems in Logic and AI"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Eiter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,9,20]]},"reference":[{"key":"53_CR1","doi-asserted-by":"publisher","first-page":"510","DOI":"10.2307\/2274239","volume":"50","author":"C. Alchourr\u00f3n","year":"1985","unstructured":"C. Alchourr\u00f3n, P. G\u00e4rdenfors, and D. Makinson. On the logic of theory change: Partial meet contraction and revision functions. J. Symb. Logic, 50:510\u2013530, 1985.","journal-title":"J. Symb. Logic"},{"issue":"2","key":"53_CR2","first-page":"119","volume":"9","author":"C. Benzaken","year":"1966","unstructured":"C. Benzaken. Algorithme de dualisation d\u2019une fonction bool\u00e9enne. Revue Francaise de Traitment de l\u2019Information-Chiffres, 9(2):119\u2013128, 1966.","journal-title":"Revue Francaise de Traitment de l\u2019Information-Chiffres"},{"key":"53_CR3","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1995.1157","volume":"123","author":"C. Bioch","year":"1995","unstructured":"C. Bioch and T. Ibaraki. Complexity of identification and dualization of positive Boolean functions. Information and Computation, 123:50\u201363, 1995.","journal-title":"Information and Computation"},{"issue":"4","key":"53_CR4","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1142\/S0129626400000251","volume":"10","author":"E. Boros","year":"2000","unstructured":"E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan. An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Processing Letters, 10(4):253\u2013266, 2000.","journal-title":"Parallel Processing Letters"},{"key":"53_CR5","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1080\/10556789808805708","volume":"10","author":"E. Boros","year":"1998","unstructured":"E. Boros, V. Gurvich, and P. L. Hammer. Dual subimplicants of positive Boolean functions. Optimization Methods and Software, 10:147\u2013156, 1998.","journal-title":"Optimization Methods and Software"},{"key":"53_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/3-540-45841-7_10","volume-title":"On the complexity of generating maximal frequent and minimal infrequent sets","author":"E. Boros","year":"2002","unstructured":"E. Boros, V. Gurvich, L. Khachiyan, and K. Makino. On the complexity of generating maximal frequent and minimal infrequent sets. In Proc. STACS-02, LNCS 2285, pp. 133\u2013141, 2002."},{"issue":"1","key":"53_CR7","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1137\/S0097539793269089","volume":"26","author":"E. Boros","year":"1997","unstructured":"E. Boros, P. Hammer, T. Ibaraki, and K. Kawakami. Polynomial time recognition of 2-monotonic positive Boolean functions given by an oracle. SIAM J. Comput., 26(1):93\u2013109, 1997.","journal-title":"SIAM J. Comput."},{"key":"53_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0004-3702(87)90063-4","volume":"32","author":"J. Kleer de","year":"1987","unstructured":"J. de Kleer and B. C. Williams. Diagnosing multiple faults. Artificial Intelligence, 32:97\u2013130, 1987.","journal-title":"Artificial Intelligence"},{"key":"53_CR9","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/A:1007627028578","volume":"37","author":"C. Domingo","year":"1999","unstructured":"C. Domingo, N. Mishra, and L. Pitt. Eficient read-restricted monotone CNF\/DNF dualization by learning with membership queries. Machine Learning, 37:89\u2013110, 1999.","journal-title":"Machine Learning"},{"key":"53_CR10","unstructured":"T. Eiter. On Transversal Hypergraph Computation and Deciding Hypergraph Saturation. PhD thesis, Institut f\u00fcr Informationssysteme, TU Wien, Austria, 1991."},{"issue":"6","key":"53_CR11","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1137\/S0097539793250299","volume":"24","author":"T. Eiter","year":"1995","unstructured":"T. Eiter and G. Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6):1278\u20131304, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"53_CR12","doi-asserted-by":"crossref","unstructured":"T. Eiter, G. Gottlob, and K. Makino. New results on monotone dualization and generating hypergraph transversals. In Proc. ACM STOC-2002, pp. 14\u201322, 2002. Full paper Tech. Rep. INFSYS RR-1843-02-05, TU Wien. Available as Computer Science Repository Report (CoRR) nr. cs.DS\/0204009 via URL: http:\/\/arxiv.org\/abs\/cs\/0204009 .","DOI":"10.1145\/509907.509912"},{"key":"53_CR13","unstructured":"T. Eiter and K. Makino. On computing all abductive explanations. In Proc. 18th National Conference on Artificial Intelligence (AAAI\u2019 02). AAAI Press, 2002."},{"issue":"1\u20132","key":"53_CR14","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1016\/S0304-3975(01)00003-2","volume":"270","author":"T. Eiter","year":"2002","unstructured":"T. Eiter, K. Makino, and T. Ibaraki. Decision lists and related Boolean functions. Theoretical Computer Science, 270(1\u20132):493\u2013524, 2002.","journal-title":"Theoretical Computer Science"},{"key":"53_CR15","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R. Fagin","year":"1983","unstructured":"R. Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. Journal of the ACM, 30:514\u2013550, 1983.","journal-title":"Journal of the ACM"},{"key":"53_CR16","doi-asserted-by":"crossref","unstructured":"R. Fagin, J. D. Ullman, and M. Y. Vardi. On the semantics of updates in databases. In Proc. PODS-83, pp. 352\u2013365, 1983.","DOI":"10.1145\/588058.588100"},{"key":"53_CR17","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"M. Fredman","year":"1996","unstructured":"M. Fredman and L. Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms, 21:618\u2013628, 1996.","journal-title":"Journal of Algorithms"},{"key":"53_CR18","unstructured":"G. Friedrich, G. Gottlob, and W. Nejdl. Physical negation instead of fault models. In Proc. AAAI-91, July 1990."},{"key":"53_CR19","unstructured":"P. G\u00e4rdenfors. Knowledge in Flux. Bradford Books, MIT Press, 1988."},{"key":"53_CR20","volume-title":"Computers and Intractability-A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. S. Johnson. Computers and Intractability-A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979."},{"key":"53_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/3-540-40992-0_16","volume-title":"Self-duality of bounded monotone Boolean functions and related problems","author":"D. Gaur","year":"2000","unstructured":"D. Gaur and R. Krishnamurti. Self-duality of bounded monotone Boolean functions and related problems. In Proc. 11th International Conference on Algorithmic Learning Theory (ALT), LNCS 1968, pp. 209\u2013223. Springer, 2000."},{"key":"53_CR22","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0004-3702(86)90067-6","volume":"30","author":"M. L. Ginsberg","year":"1986","unstructured":"M. L. Ginsberg. Counterfactuals. Artificial Intelligence, 30:35\u201379, 1986.","journal-title":"Artificial Intelligence"},{"key":"53_CR23","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0004-3702(88)90011-2","volume":"35","author":"M. L. Ginsberg","year":"1988","unstructured":"M. L. Ginsberg and D. E. Smith. Reasoning about action I: A possible worlds approach. Artificial Intelligence, 35:165\u2013195, 1988.","journal-title":"Artificial Intelligence"},{"key":"53_CR24","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1613\/jair.380","volume":"8","author":"G. Gogic","year":"1998","unstructured":"G. Gogic, C. Papadimitriou, and M. Sideri. Incremental recompilation of knowledge. J. Artificial Intelligence Research, 8:23\u201337, 1998.","journal-title":"J. Artificial Intelligence Research"},{"issue":"2","key":"53_CR25","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/235767.235769","volume":"27","author":"J. Goldsmith","year":"1978","unstructured":"J. Goldsmith, M. Levy, and M. Mundhenk. Limited nondeterminism. SIGACT News, 27(2):20\u201329, 1978.","journal-title":"SIGACT News"},{"key":"53_CR26","doi-asserted-by":"crossref","unstructured":"G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. In Proc. 18th ACM Symp. on Principles of Database Systems (PODS-99), pp. 21\u201332, 1999. Full paper to appear in Journal of Computer and System Sciences.","DOI":"10.1145\/303976.303979"},{"issue":"4","key":"53_CR27","first-page":"385","volume":"9","author":"G. Gottlob","year":"1990","unstructured":"G. Gottlob and L. Libkin. Investigations on Armstrong relations, dependency inference, and excluded functional dependencies. Acta Cybernetica, 9(4):385\u2013402, 1990.","journal-title":"Acta Cybernetica"},{"key":"53_CR28","doi-asserted-by":"crossref","unstructured":"D. Gunopulos, R. Khardon, H. Mannila, and H. Toivonen. Data mining, hypergraph transversals, and machine learning. In Proc. 16th ACM Symp. on Principles of Database Systems (PODS-97), pp. 209\u2013216, 1997.","DOI":"10.1145\/263661.263684"},{"key":"53_CR29","doi-asserted-by":"crossref","unstructured":"D. S. Johnson. A Catalog of Complexity Classes. In J. van Leeuwen, ed., Handbook of Theoretical Computer Science, A, chapter 2. Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"53_CR30","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D. S. Johnson","year":"1988","unstructured":"D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27:119\u2013123, 1988.","journal-title":"Information Processing Letters"},{"key":"53_CR31","unstructured":"H. Kautz, M. Kearns, and B. Selman. Reasoning with characteristic models. In Proc. AAAI-93, pp. 34\u201339, 1993."},{"key":"53_CR32","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/3-540-57568-5_271","volume-title":"On Horn envelopes and hypergraph transversals","author":"D. Kavvadias","year":"1993","unstructured":"D. Kavvadias, C. Papadimitriou, and M. Sideri. On Horn envelopes and hypergraph transversals. In W. Ng, editor, Proc. 4th International Symposium on Algorithms and Computation (ISAAC-93), LNCS 762, pp. 399\u2013405, 1993."},{"key":"53_CR33","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1613\/jair.183","volume":"3","author":"R. Khardon","year":"1995","unstructured":"R. Khardon. Translating between Horn representations and their characteristic models. J. Artificial Intelligence Research, 3:349\u2013372, 1995.","journal-title":"J. Artificial Intelligence Research"},{"key":"53_CR34","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(85)90227-0","volume":"38","author":"N. Linial","year":"1985","unstructured":"N. Linial and M. Tarsi. Deciding hypergraph 2-colorability by H-resolution. Theoretical Computer Science, 38:343\u2013347, 1985.","journal-title":"Theoretical Computer Science"},{"key":"53_CR35","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1006\/jagm.1997.0896","volume":"26","author":"K. Makino","year":"1998","unstructured":"K. Makino and T. Ibaraki. A fast and simple algorithm for identifying 2-monotonic positive Boolean functions. Journal of Algorithms, 26:291\u2013302, 1998.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"53_CR36","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/0022-0000(86)90015-2","volume":"22","author":"H. Mannila","year":"1986","unstructured":"H. Mannila and K.-J. R\u00e4ih\u00e4. Design by Example: An application of Armstrong relations. Journal of Computer and System Sciences, 22(2):126\u2013141, 1986.","journal-title":"Journal of Computer and System Sciences"},{"key":"53_CR37","doi-asserted-by":"crossref","unstructured":"N. Mishra and L. Pitt. Generating all maximal independent sets of boundeddegree hypergraphs. In Proc. Tenth Annual Conference on Computational Learning Theory (COLT-97), pp. 211\u2013217, 1997.","DOI":"10.1145\/267460.267500"},{"key":"53_CR38","unstructured":"B. Nebel. A knowledge level analysis of belief revision. In Proc. 1st Intl. Conf. on Principles of Knowledge Representation and Reasoning (KR-89), pp. 301\u2013311, 1989."},{"key":"53_CR39","doi-asserted-by":"crossref","unstructured":"B. Nebel. How Hard is it to Revise a Belief Base? In D. Gabbay and Ph. Smets, eds, Handbook on Defeasible Reasoning and Uncertainty Management Systems, volume III: Belief Change, pp. 77\u2013145. Kluwer Academic, 1998.","DOI":"10.1007\/978-94-011-5054-5_3"},{"key":"53_CR40","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"53_CR41","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0004-3702(87)90062-2","volume":"32","author":"R. Reiter","year":"1987","unstructured":"R. Reiter. A theory of diagnosis from first principles. Artificial Intelligence, 32:57\u201395, 1987.","journal-title":"Artificial Intelligence"},{"key":"53_CR42","unstructured":"B. Selman and H. J. Levesque. Abductive and default reasoning: A computational core. In Proc. AAAI-90, pp. 343\u2013348, 1990."},{"key":"53_CR43","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0020-0190(00)00225-8","volume":"79","author":"I. Shmulevich","year":"2001","unstructured":"I. Shmulevich, A. Korshunov, and J. Astola. Almost all monotone boolean functions are polynomially learnable using membership queries. Information Processing Letters, 79:211\u2013213, 2001.","journal-title":"Information Processing Letters"},{"key":"53_CR44","unstructured":"K. Takata. On the sequential method for listing minimal hitting sets. In Proc. Workshop on Discrete Mathematics and Data Mining, 2nd SIAM International Conference on Data Mining, April 11\u201313, Arlington, Virginia, USA, 2002."},{"key":"53_CR45","doi-asserted-by":"crossref","unstructured":"M. Winslett. Updating Logical Databases. Cambridge University Press, 1990.","DOI":"10.1017\/CBO9780511663109"}],"container-title":["Lecture Notes in Computer Science","Logics in Artificial Intelligence"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45757-7_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T18:08:03Z","timestamp":1556906883000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45757-7_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441908","9783540457572"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/3-540-45757-7_53","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}