{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:25:31Z","timestamp":1725513931666},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540727873"},{"type":"electronic","value":"9783540727880"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72788-0_20","type":"book-chapter","created":{"date-parts":[[2007,6,28]],"date-time":"2007-06-28T12:25:22Z","timestamp":1183033522000},"page":"187-200","source":"Crossref","is-referenced-by-count":4,"title":["On the Boolean Connectivity Problem for Horn Relations"],"prefix":"10.1007","author":[{"given":"Kazuhisa","family":"Makino","sequence":"first","affiliation":[]},{"given":"Suguru","family":"Tamaki","sequence":"additional","affiliation":[]},{"given":"Masaki","family":"Yamamoto","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Information Processing Letters\u00a08, 121\u2013123 (1979)","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Ricci-Tersenghi, F.: On the solution-space geometry of random constraint satisfaction problems. In: Proceeding of 38th ACM Symposium on Theory of Computing, pp. 130\u2013139 (2006)","key":"20_CR2","DOI":"10.1145\/1132516.1132537"},{"issue":"1","key":"20_CR3","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1137\/S0097539792228629","volume":"23","author":"E. Boros","year":"1994","unstructured":"Boros, E., et al.: A Complexity Index for Satisfiability Problems. SIAM J. Comput.\u00a023(1), 45\u201349 (1994)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proceeding of 43rd IEEE Symposium on Foundations of Computer Science, pp. 649\u2013658 (2002)","key":"20_CR4","DOI":"10.1109\/SFCS.2002.1181990"},{"issue":"1","key":"20_CR5","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1145\/102782.102789","volume":"38","author":"V. Chandru","year":"1991","unstructured":"Chandru, V., Hooker, J.N.: Extended Horn sets in propositional logic. J. ACM\u00a038(1), 205\u2013221 (1991)","journal-title":"J. ACM"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N. Creignou","year":"1995","unstructured":"Creignou, N.: A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences\u00a051, 511\u2013522 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Information and Computation\u00a0125, 1\u201312 (1996)","journal-title":"Information and Computation"},{"doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity classification of Boolean constraint satisfaction problems. SIAM Monographs on Discrete Mathematics and Applications (2001)","key":"20_CR8","DOI":"10.1137\/1.9780898718546"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/S0097539704446311","volume":"36","author":"N. Creignou","year":"2006","unstructured":"Creignou, N., Zanuttini, B.: A complete classification of the complexity of propositional abduction. SIAM Journal on Computing\u00a036, 207\u2013229 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0004-3702(92)90009-M","volume":"58","author":"R. Dechter","year":"1992","unstructured":"Dechter, R., Pearl, J.: Structure identification in relational data. Artificial Intelligence\u00a058, 237\u2013270 (1992)","journal-title":"Artificial Intelligence"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0004-3702(99)00021-1","volume":"110","author":"T. Eiter","year":"1999","unstructured":"Eiter, T., Ibaraki, T., Makino, K.: Computing intersections of Horn theories for reasoning with models. Artificial Intelligence\u00a0110, 57\u2013101 (1999)","journal-title":"Artificial Intelligence"},{"unstructured":"Eiter, T., Makino, K.: Generating all abductive explanations for queries on propositional Horn theories. KBS Research Report INFSYS RR-1843-03-09, Institute of Information Systems, Vienna University of Technology (2006)","key":"20_CR12"},{"unstructured":"Eiter, T., Makino, K., Gottlob, G.: Computational aspects of monotone dualization: A brief survey. KBS Research Report INFSYS RR-1843-06-01, Institute of Information Systems, Vienna University of Technology (2006)","key":"20_CR13"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0166-218X(99)00098-0","volume":"96-97","author":"O. Ekin","year":"1999","unstructured":"Ekin, O., Hammer, P.L., Kogan, A.: On connected Boolean functions. Discrete Applied Mathematics\u00a096-97, 337\u2013362 (1999)","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR15","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, 618\u2013628 (1996)","journal-title":"Journal of Algorithms"},{"key":"20_CR16","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H.\u00a0Freeman and Company, New York (1978)"},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","first-page":"346","volume-title":"Automata, Languages and Programming","author":"P.G. Kolaitis","year":"2006","unstructured":"Kolaitis, P.G., et al.: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. In: Bugliesi, M., et al. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 346\u2013357. Springer, Heidelberg (2006)"},{"key":"20_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/3-540-48321-7_27","volume-title":"Fundamentals of Computation Theory","author":"L. Juban","year":"1999","unstructured":"Juban, L.: Dichotomy theorem for the generalize unique satisfiability problem. In: Ciobanu, G., P\u0103un, G. (eds.) FCT 1999. LNCS, vol.\u00a01684, pp. 327\u2013337. Springer, Heidelberg (1999)"},{"key":"20_CR19","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/S0890-5401(03)00037-3","volume":"187","author":"L. Kirousis","year":"2003","unstructured":"Kirousis, L., Kolaitis, P.: The complexity of minimal satisfiability problems. Information and Computation\u00a0187, 20\u201339 (2003)","journal-title":"Information and Computation"},{"unstructured":"Kautz, H., Kearns, M., Selman, B.: Reasoning With characteristic models. In: Proceedings AAAI-93, pp. 34\u201339 (1993)","key":"20_CR20"},{"key":"20_CR21","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0004-3702(94)00072-9","volume":"74","author":"H. Kautz","year":"1995","unstructured":"Kautz, H., Kearns, M., Selman, B.: Horn approximations of empirical data. Artificial Intelligence\u00a074, 129\u2013245 (1995)","journal-title":"Artificial Intelligence"},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/3-540-57568-5_271","volume-title":"Algorithms and Computation","author":"D. Kavvadias","year":"1993","unstructured":"Kavvadias, D., Papadimitriou, C., Sideri, M.: On Horn envelopes and hypergraph transversals. In: Ng, K.W., et al. (eds.) ISAAC 1993. LNCS, vol.\u00a0762, pp. 399\u2013405. Springer, Heidelberg (1993)"},{"key":"20_CR23","first-page":"349","volume":"3","author":"R. Khardon","year":"1995","unstructured":"Khardon, R.: Translating between Horn representations and their characteristic models. Journal of AI Research\u00a03, 349\u2013372 (1995)","journal-title":"Journal of AI Research"},{"issue":"1-2","key":"20_CR24","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0004-3702(96)00006-9","volume":"87","author":"R. Khardon","year":"1996","unstructured":"Khardon, R., Roth, D.: Reasoning with models. Artificial Intelligence\u00a087(1-2), 187\u2013213 (1996)","journal-title":"Artificial Intelligence"},{"key":"20_CR25","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0004-3702(97)00044-1","volume":"97","author":"R. Khardon","year":"1997","unstructured":"Khardon, R., Roth, D.: Defaults and relevance in model-based reasoning. Artificial Intelligence\u00a097, 169\u2013193 (1997)","journal-title":"Artificial Intelligence"},{"key":"20_CR26","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1137\/S0097539795285114","volume":"28","author":"D. Kavvadias","year":"1998","unstructured":"Kavvadias, D., Sideri, M.: The inverse satisfiability problem. SIAM Journal on Computing\u00a028, 152\u2013163 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR27","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2001","unstructured":"Khanna, S., et al.: The approximability of constraint satisfaction problems. SIAM Journal on Computing\u00a030, 1863\u20131920 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR28","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1145\/322047.322059","volume":"25","author":"H.R. Lewis","year":"1978","unstructured":"Lewis, H.R.: Renaming a set of clauses as a Horn set. J. ACM\u00a025, 134\u2013135 (1978)","journal-title":"J. ACM"},{"key":"20_CR29","doi-asserted-by":"publisher","first-page":"61","DOI":"10.2307\/2268172","volume":"8","author":"J. McKinsey","year":"1943","unstructured":"McKinsey, J.: The decision problem for some classes of sentences without quantifiers. Journal of Symbolic Logic\u00a08, 61\u201376 (1943)","journal-title":"Journal of Symbolic Logic"},{"doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceeding of 10th ACM Symposium of Theory of Computing, pp. 216\u2013226 (1978)","key":"20_CR30","DOI":"10.1145\/800133.804350"},{"key":"20_CR31","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol.\u00a024. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72788-0_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:05:06Z","timestamp":1605762306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72788-0_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540727873","9783540727880"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72788-0_20","relation":{},"subject":[]}}