{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T06:05:37Z","timestamp":1747548337061},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1996,9,1]],"date-time":"1996-09-01T00:00:00Z","timestamp":841536000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[1996,9]]},"DOI":"10.1007\/bf02127974","type":"journal-article","created":{"date-parts":[[2005,9,14]],"date-time":"2005-09-14T17:08:51Z","timestamp":1126717731000},"page":"339-357","source":"Crossref","is-referenced-by-count":7,"title":["Hierarchies of polynomially solvable satisfiability problems"],"prefix":"10.1007","volume":"17","author":[{"given":"Daniele","family":"Pretolani","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02127974_CR1","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0743-1066(91)90006-B","volume":"10","author":"G. Ausiello","year":"1991","unstructured":"G. Ausiello and G.F. Italiano, On line algorithms for polynomially solvable satisfiability problems,J. Logic Programming 10 (1991) 69\u201390.","journal-title":"J. Logic Programming"},{"key":"BF02127974_CR2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01531068","volume":"1","author":"E. Boros","year":"1990","unstructured":"E. Boros, Y. Crama and P.L. Hammer, Polynomial time inference of all valid implications for Horn and related formulas,Ann. Math. Artificial Intelligence 1 (1990) 21\u201332.","journal-title":"Ann. Math. Artificial Intelligence"},{"issue":"2","key":"BF02127974_CR3","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/0304-3975(93)90331-M","volume":"116","author":"H. Kleine B\u00fcning","year":"1993","unstructured":"H. Kleine B\u00fcning, On generalized Horn formulas andk-resolution,Theoret. Comput. Sci. 116(2) (1993) 405\u2013413.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02127974_CR4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF01531069","volume":"1","author":"V. Chandru","year":"1990","unstructured":"V. Chandru, V. Coullard, P.L. Hammer, M. Monta\u00f1ez and X. Sun, On renamable Horn and generalized Horn functions,Ann. Math. Artificial Intelligence 1 (1990) 33\u201348.","journal-title":"Ann. Math. Artificial Intelligence"},{"key":"BF02127974_CR5","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/102782.102789","volume":"38","author":"V. Chandru","year":"1991","unstructured":"V. Chandru and J.N. Hooker, Extended Horn sets in propositional logic,J. Assoc. Comput. Mach. 38 (1991) 205\u2013221.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02127974_CR6","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0020-0190(92)90081-6","volume":"44","author":"M. Dalal","year":"1992","unstructured":"M. Dalal and D.W. Etherington, A hierarchy of tractable satisfiability problems,Inform. Process. Lett. 44 (1992) 173\u2013180.","journal-title":"Inform. Process. Lett."},{"key":"BF02127974_CR7","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"3","author":"W. Dowling","year":"1984","unstructured":"W. Dowling and J. Gallier, Linear-time algorithms for testing the satisfiability of propositional Horn formulae,J. Logic Programming 3 (1984) 267\u2013284.","journal-title":"J. Logic Programming"},{"issue":"2","key":"BF02127974_CR8","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0166-218X(93)E0152-O","volume":"59","author":"T. Eiter","year":"1995","unstructured":"T. Eiter, P. Kilpel\u00e4inen and H. Mannila, Recognizing renamable generalized propositional Horn formulas is NP-Complete,Discrete Appl. Math. 59(2) (1995) 23\u201332.","journal-title":"Discrete Appl. Math."},{"key":"BF02127974_CR9","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0020-0190(88)90113-5","volume":"29","author":"G. Gallo","year":"1988","unstructured":"G. Gallo and M.G. Scutell\u00e0, Polynomially solvable satisfiability problems,Inform. Process. Lett. 29 (1988) 221\u2013227.","journal-title":"Inform. Process. Lett."},{"key":"BF02127974_CR10","unstructured":"D. Loveland,Automated Theorem Proving: A Logical Basis (North-Holland, 1978)."},{"key":"BF02127974_CR11","volume-title":"Satisfiability and Hypergraphs","author":"D. Pretolani","year":"1993","unstructured":"D. Pretolani,Satisfiability and Hypergraphs, Ph.D. Thesis, Department of Computer Science, University of Pisa, Italy (March, 1993) TD-12\/93."},{"key":"BF02127974_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(83)80027-8","volume":"59","author":"S. Yamasaki","year":"1983","unstructured":"S. Yamasaki and S. Doshita, The satisfiability problem for a class consisting of Horn sentences and some non-Horn sentences in proportional logic,Inform. and Control 59 (1983) 1\u201312.","journal-title":"Inform. and Control"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02127974.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02127974\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02127974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T01:45:41Z","timestamp":1557798341000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02127974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["BF02127974"],"URL":"https:\/\/doi.org\/10.1007\/bf02127974","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}