×

zbMATH — the first resource for mathematics

Backdoors to normality for disjunctive logic programs. (English) Zbl 1367.68032

MSC:
68N17 Logic programming
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdelwaheb Ayari and David A. Basin. 2002. QUBOS: Deciding quantified Boolean logic using propositional satisfiability solvers. In Proceedings of the 4th International Conference on Formal Methods in Computer-Aided Design (FMCAD’02) (Lecture Notes in Computer Science), Mark Aagaard and John W. O’Leary (Eds.), Vol. 2517. Springer Verlag, Portland, OR, 187–201. DOI:http://dx.doi.org/10.1007/3-540-36126-X_12 · Zbl 1019.68597 · doi:10.1007/3-540-36126-X_12
[2] Yuliya Babovich, Esra Erdem, and Vladimir Lifschitz. 2000. Fages’ theorem and answer set programming. In Proceedings of the 8th International Workshop on Non-Monotonic Reasoning (NMR’00), Chitta Baral and Mirosław Truszczyński (Eds.). arXiv:cs/0003042.
[3] Rachel Ben-Eliyahu and Rina Dechter. 1994. Propositional semantics for disjunctive logic programs. Annals of Mathematics and Artificial Intelligence 12, 1, 53–87. DOI:http://dx.doi.org/10.1007/BF01530761 · Zbl 0858.68012 · doi:10.1007/BF01530761
[4] Nicole Bidoít and Christine Froidevaux. 1991. Negation by default and unstratifiable logic programs. Theoretical Computer Science 78, 1, 85–112. DOI:http://dx.doi.org/10.1016/0304-3975(51)90004-7 · Zbl 0716.68075 · doi:10.1016/0304-3975(51)90004-7
[5] Armin Biere. 2004. Resolve and expand. In Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT’04) (Lecture Notes in Computer Science), Holger H. Hoos and David G. Mitchell (Eds.). Springer Verlag, Vancouver, BC, Canada, 59–70. DOI:http://dx.doi.org/10.1007/11527695_5 · Zbl 1122.68585 · doi:10.1007/11527695_5
[6] Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.). 2009. Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, Vol. 185. IOS Press, Amsterdam, Netherlands. · Zbl 1183.68568
[7] Stefan Brass and Jürgen Dix. 1998. Characterizations of the disjunctive well-founded semantics: Confluent calculi and iterated GCWA. Journal of Automated Reasoning 20, 1, 143–165. DOI:http://dx.doi.org/10.1023/A:1005952908693 · Zbl 0893.68026 · doi:10.1023/A:1005952908693
[8] Gerhard Brewka, Thomas Eiter, and Mirosław Truszczyński. 2011. Answer set programming at a glance. Communications of the ACM 54, 12, 92–103. DOI:http://dx.doi.org/10.1145/2043174.2043195 · doi:10.1145/2043174.2043195
[9] Francesco Calimeri, Giovambattista Ianni, and Francesco Ricca. 2014. The third open answer set programming competition. Theory and Practice of Logic Programming 14, 1 (2014), 117–135. DOI:http://dx.doi.org/10.1017/S1471068412000105 · Zbl 06285650 · doi:10.1017/S1471068412000105
[10] Hubie Chen and Yannet Interian. 2005. A model for generating random quantified Boolean formulas. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI’05), Leslie Pack Kaelbling and Alessandro Saffiotti (Eds.). Professional Book Center, Edinburgh, Scotland, UK, 66–71. · Zbl 1122.68602
[11] J. Chen, I. Kanj, and G. Xia. 2006. Improved parameterized upper bounds for vertex cover. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS’06) (Lecture Notes in Computer Science), Rastislav Královič and Paweł Urzyczyn (Eds.), Vol. 4162. Springer Verlag, Stará Lesná, Slovakia, 238–249. DOI:http://dx.doi.org/10.1007/11821069_21 · Zbl 1132.68421 · doi:10.1007/11821069_21
[12] Keith L. Clark. 1978. Negation as failure. Logic and Data Bases 1, 293–322. · doi:10.1007/978-1-4684-3384-5_11
[13] Ronald DeHaan and Stefan Szeider. 2014a. Fixed-parameter tractable reductions to SAT. In Proceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT’14) (Lecture Notes in Computer Science), Carsten Sinz and Uwe Egly (Eds.), Vol. 8561. Springer Verlag, Vienna, Austria, 85–102. DOI:http://dx.doi.org/10.1007/978-3-319-09284-3_8 Held as part of the Vienna Summer of Logic, VSL 2014. · Zbl 1423.68444 · doi:10.1007/978-3-319-09284-3_8
[14] Ronald DeHaan and Stefan Szeider. 2014b. The parameterized complexity of reasoning problems beyond NP. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR’14), Chitta Baral, Giuseppe De Giacomo, and Thomas Eiter (Eds.). AAAI Press, Held as part of the Vienna Summer of Logic, VSL 2014. Full version CoRR: 1312.1672.
[15] William F. Dowling and Jean H. Gallier. 1984. Linear-time algorithms for testing the satisfiability of propositional Horn formulae. Journal of Logic Programming 1, 3, 267–284. DOI:http://dx.doi.org/10.1016/0743-1066(84)90014-1 · Zbl 0593.68062 · doi:10.1016/0743-1066(84)90014-1
[16] Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer Verlag, New York. DOI:http://dx.doi.org/10.1007/978-1-4612-0515-9 · Zbl 0961.68533 · doi:10.1007/978-1-4612-0515-9
[17] Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer-Verlag, London. DOI:http://dx.doi.org/10.1007/978-1-4471-5559-1 · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1
[18] Christian Drescher, Martin Gebser, Torsten Grote, Benjamin Kaufmann, Arne König, Max Ostrowski, and Torsten Schaub. 2008. Conflict-driven disjunctive answer set solving. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR’08), Gerhard Brewka and Jérôme Lang (Eds.). AAAI Press, 422–432.
[19] Heinz-Dieter Ebbinghaus and Jörg Flum. 1999. Finite Model Theory (2nd ed.). Springer-Verlag, Berlin. · Zbl 0932.03032
[20] Uwe Egly, Thomas Eiter, Volker Klotz, Hans Tompits, and Stefan Woltran. 2001. Computing stable models with quantified Boolean formulas: Some experimental results. In Proceedings of the 1st International Workshop on Answer Set Programming (ASP’01), Towards Efficient and Scalable Knowledge Representation and Reasoning, Alessandro Provetti and Tran Cao Son (Eds.). AAAI Press, 7.
[21] Uwe Egly, Thomas Eiter, Hans Tompits, and Stefan Woltran. 2000. Solving advanced reasoning tasks using quantified Boolean formulas. In Proceedings of the 17th Conference on Artificial Intelligence (AAAI’00), Henry Kautz and Bruce Porter (Eds.). AAAI Press, 417–422.
[22] Uwe Egly, Florian Lonsing, and Magdalena Widl. 2013. Long-distance resolution: Proof generation and strategy extraction in search-based QBF solving. In Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR’13) (Lecture Notes in Computer Science), Ken McMillan, Aart Middeldorp, and Andrei Voronkov (Eds.), Vol. 8312. Springer Verlag, Stellenbosch, South Africa, 291–308. DOI:http://dx.doi.org/10.1007/978-3-642-45221-5_21 · Zbl 1406.68106 · doi:10.1007/978-3-642-45221-5_21
[23] Thomas Eiter, Michael Fink, Hans Tompits, and Stefan Woltran. 2004a. On eliminating disjunctions in stable logic programming. In Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning (KR’04), Anthony G. Cohn (Ed.). AAAI Press, 447–458. · Zbl 1122.68369
[24] Thomas Eiter, Michael Fink, Hans Tompits, and Stefan Woltran. 2004b. Simplifying logic programs under uniform and strong equivalence. In Proceedings 7th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’04) (Lecture Notes in Computer Science), Ilkka Niemelä and Vladimir Lifschitz (Eds.), Vol. 2923. Springer-Verlag, 87–99. DOI:http://dx.doi.org/10.1007/978-3-540-24609-1_10 · Zbl 1122.68369 · doi:10.1007/978-3-540-24609-1_10
[25] Thomas Eiter and Georg Gottlob. 1995. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence 15, 3–4, 289–323. DOI:http://dx.doi.org/10.1007/BF01536399 · Zbl 0858.68016 · doi:10.1007/BF01536399
[26] Ulle Endriss, Ronald De Haan, and Stefan Szeider. 2014. Parameterized complexity results for agenda safety in judgment aggregation. In Proceedings of the 5th International Workshop on Computational Social Choice (COMSOC’14), Ariel Procaccia and Toby Walsh (Eds.). Carnegie Mellon University, Pittsburgh, PA.
[27] Francois Fages. 1994. Consistency of Clark’s completion and existence of stable models. Journal on Methods of Logic in Computer Science 1, 1, 51–60.
[28] Johannes K. Fichte and Stefan Szeider. 2013. Backdoors to normality for disjunctive logic programs. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI’13), Marie des Jardins and Michael Littman (Eds.). AAAI Press, 320–327. A preliminary version of the paper was presented on the Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP’12).
[29] Johannes K. Fichte and Stefan Szeider. 2015. Backdoors to tractable answer-set programming. Artificial Intelligence 220, 0, 64–103. DOI:http://dx.doi.org/10.1016/j.artint.2014.12.001 Extended and updated version of a paper that appeared in Proceedings of the 22nd International Conference on Artificial Intelligence (IJCAI’11). · Zbl 1328.68040 · doi:10.1016/j.artint.2014.12.001
[30] Johannes K. Fichte, Mirosław Truszczyński, and Stefan Woltran. 2015. Dual-normal programs – The forgotten class. Theory and Practice of Logic Programming 15, 04-05, 495–510. Special issue on the 31st International Conference on Logic Programming (ICLP’15).
[31] Jörg Flum and Martin Grohe. 2003. Describing parameterized complexity classes. Information and Computation 187, 2, 291–319. DOI:http://dx.doi.org/10.1016/S0890-5401(03)00161-5 · Zbl 1076.68031 · doi:10.1016/S0890-5401(03)00161-5
[32] Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Theoretical Computer Science, Vol. XIV. Springer Verlag, Berlin. 495 pages. DOI:http://dx.doi.org/10.1007/3-540-29953-X · doi:10.1007/3-540-29953-X
[33] Serge Gaspers and Stefan Szeider. 2012. Backdoors to satisfaction. In The Multivariate Algorithmic Revolution and Beyond, Hans Bodlaender, Rod Downey, Fedor Fomin, and Dániel Marx (Eds.). Lecture Notes in Computer Science, Vol. 7370. Springer-Verlag, Berlin, 287–317. DOI:http://dx.doi.org/10.1007/978-3-642-30891-8_15 · Zbl 1358.68133 · doi:10.1007/978-3-642-30891-8_15
[34] Martin Gebser, Tomi Janhunen, and Jussi Rintanen. 2014. Answer set programming as SAT modulo acyclicity. In Proceedings of the 21st Eureopean Conference on Artificial Intelligence (ECAI’14) (Frontiers in Artificial Intelligence and Applications), Torsten Schaub, Gerhard Friedrich, and Barry O’Sullivan (Eds.), Vol. 263. IOS Press, Prague, Czech Republic, 351–356. DOI:http://dx.doi.org/10.3233/978-1-61499-419-0-351 · Zbl 1366.68017
[35] Martin Gebser and Roland Kaminski. 2012. Personal communication.
[36] Martin Gebser, Benjamin Kaufmann, Roland Kaminski, Max Ostrowski, Torsten Schaub, and Marius Schneider. 2011. Potassco: The Potsdam answer set solving collection. AI Communications 24, 2, 107–124. DOI:http://dx.doi.org/10.3233/AIC-2011-0491 · Zbl 1215.68214
[37] Martin Gebser, Benjamin Kaufmann, and Torsten Schaub. 2013. Advanced conflict-driven disjunctive answer set solving. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13), Francesca Rossi and Sebastian Thrun (Eds.). The AAAI Press, Beijing, China, 912–918. · Zbl 1251.68060
[38] Martin Gebser, Lengning Liu, Gayathri Namasivayam, André Neumann, Torsten Schaub, and Mirosław Truszczyński. 2007. The first answer set programming system competition. In Proceedings of the 9th Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’07) (Lecture Notes in Computer Science), Chitta Baral, Gerhard Brewka, and John Schlipf (Eds.), Vol. 4483. Springer-Verlag, 3–17. DOI:http://dx.doi.org/10.1007/978-3-540-72200-7_3 · Zbl 05211322 · doi:10.1007/978-3-540-72200-7_3
[39] Martin Gebser, Torsten Schaub, Sven Thiele, and Philippe Veber. 2011. Detecting inconsistencies in large biological networks with answer set programming. Theory and Practice of Logic Programming 11, 2–3, 323–360. · Zbl 1220.68036 · doi:10.1017/S1471068410000554
[40] Michael Gelfond and Vladimir Lifschitz. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference and Symposium on Logic Programming (ICLP/SLP’88), Robert A. Kowalski and Kenneth A. Bowen (Eds.), Vol. 2. MIT Press, 1070–1080.
[41] Michael Gelfond and Vladimir Lifschitz. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 3/4, 365–386. DOI:http://dx.doi.org/10.1007/BF03037169 · Zbl 0735.68012 · doi:10.1007/BF03037169
[42] Enrico Giunchiglia, Yuliya Lierler, and Marco Maratea. 2006. Answer set programming based on propositional satisfiability. Journal of Automated Reasoning 36, 4, 345–377. DOI:http://dx.doi.org/10.1007/s10817-006-9033-2 · Zbl 1107.68029 · doi:10.1007/s10817-006-9033-2
[43] Carla P. Gomes, Henry Kautz, Ashish Sabharwal, and Bart Selman. 2008. Chapter 2: Satisfiability solvers. In Handbook of Knowledge Representation, Vladimir Lifschitz, Frank van Harmelen, and Bruce Porter (Eds.). Foundations of Artificial Intelligence, Vol. 3. Elsevier Science Publishers, North-Holland, Amsterdam, Netherlands, Chapter 2, 89–134. DOI:http://dx.doi.org/10.1016/S1574-6526(07)03002-7 · doi:10.1016/S1574-6526(07)03002-7
[44] Georg Gottlob and Stefan Szeider. 2008. Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems. Computing Journal 51, 3, 303–325. DOI:http://dx.doi.org/10.1093/comjnl/bxm056 · Zbl 05534223 · doi:10.1093/comjnl/bxm056
[45] Alexandra Goultiaeva, Martina Seidl, and Armin Biere. 2013. Bridging the gap between dual propagation and CNF-based QBF solving. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE’13). EDA Consortium, Grenoble, France, 811–814. · doi:10.7873/DATE.2013.172
[46] Tomi Janhunen. 2006. Some (in)translatability results for normal logic programs and propositional theories. Journal of Applied Non-Classical Logics 16, 1–2, 35–86. DOI:http://dx.doi.org/10.3166/jancl.16.35-86 · Zbl 1184.68160 · doi:10.3166/jancl.16.35-86
[47] Tomi Janhunen, Ilkka Niemelä, Dietmar Seipel, Patrik Simons, and Jia-Huai You. 2006. Unfolding partiality and disjunctions in stable model semantics. ACM Transactions on Computer Logic 7, 1, 1–37. DOI:http://dx.doi.org/10.1145/1119439.1119440 · Zbl 1367.68035 · doi:10.1145/1119439.1119440
[48] Tomi Janhunen, Ilkka Niemelä, and Mark Sevalnev. 2009. Computing stable models via reductions to difference logic. In Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’09) (Lecture Notes in Computer Science), Esra Erdem, Fangzhen Lin, and Torsten Schaub (Eds.), Vol. 5753. Springer-Verlag, 142–154. DOI:http://dx.doi.org/10.1007/978-3-642-04238-6_14 · Zbl 1258.68030 · doi:10.1007/978-3-642-04238-6_14
[49] Tomi Janhunen, Emilia Oikarinen, Hans Tompits, and Stefan Woltran. 2009. Modularity aspects of disjunctive stable models. Journal of Artificial Intelligence Research 35, 2, 813–857. DOI:http://dx.doi.org/10.1613/jair.2810 · Zbl 1192.68129
[50] Mikoláš Janota and Joao Marques-Silva. 2011. A tool for circumscription-based MUS membership testing. In Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’11) (Lecture Notes in Computer Science), James P. Delgrande and Wolfgang Faber (Eds.), Vol. 6645. Springer-Verlag, 266–271. DOI:http://dx.doi.org/10.1007/978-3-642-20895-9_30 · Zbl 05900007 · doi:10.1007/978-3-642-20895-9_30
[51] Hadi Katebi, Karem A. Sakallah, and João P. Marques-Silva. 2011. Empirical study of the anatomy of modern SAT solvers. In Proceedings of the 14th International Conference on Theory and Applications of Satisfiability Testing (SAT’11) (Lecture Notes in Computer Science), Karem A. Sakallah and Laurent Simon (Eds.), Vol. 6695. Springer-Verlag, 343–356. DOI:http://dx.doi.org/10.1007/978-3-642-21581-0_27 · Zbl 1330.68271 · doi:10.1007/978-3-642-21581-0_27
[52] Hans Kleine Büning and Theodor Lettman. 1999. Propositional Logic: Deduction and Algorithms. Cambridge University Press, Cambridge/New York, NY, 420 pages.
[53] Joohyung Lee. 2005. A model-theoretic counterpart of loop formulas. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI’05), Leslie Pack Kaelbling and Alessandro Saffiotti (Eds.), Vol. 19. Professional Book Center, Edinburgh, Scotland, UK, 503–508.
[54] Joohyung Lee and Vladimir Lifschitz. 2003. Loop formulas for disjunctive logic programs. In Proceedings of the 19th International Conference on Logic Programming (LP’03) (Lecture Notes in Computer Science), Catuscia Palamidessi (Ed.), Vol. 2916. Springer-Verlag, 451–465. DOI:http://dx.doi.org/10.1007/978-3-540-24599-5_31 · doi:10.1007/978-3-540-24599-5_31
[55] Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri, and Francesco Scarcello. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computer Logic 7, 3, 499–562. DOI:http://dx.doi.org/10.1145/1149114.1149117 · Zbl 1367.68308 · doi:10.1145/1149114.1149117
[56] Yuliya Lierler. 2005. CMODELS – SAT-based disjunctive answer set solver. In Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’05) (Lecture Notes in Computer Science), Chitta Baral, Gianluigi Greco, Nicola Leone, and Giorgio Terracina (Eds.), Vol. 3662. Springer-Verlag, 447–451. DOI:http://dx.doi.org/10.1007/11546207_44 · doi:10.1007/11546207_44
[57] Vladimir Lifschitz and Alexander Razborov. 2006. Why are there so many loop formulas? ACM Transactions on Computer Logic 7, 2, 261–268. DOI:http://dx.doi.org/10.1145/1131313.1131316 · Zbl 1367.68036 · doi:10.1145/1131313.1131316
[58] Fangzhen Lin and Yuting Zhao. 2004. ASSAT: Computing answer sets of a logic program by SAT solvers. Artificial Intelligence 157, 1–2, 115–137. DOI:http://dx.doi.org/10.1016/j.artint.2004.04.004 · Zbl 1085.68544 · doi:10.1016/j.artint.2004.04.004
[59] Florian Lonsing and Armin Biere. 2010. DepQBF: A dependency-aware QBF solver system description. Journal on Satisfiability, Boolean Modeling and Computation 7, 71–76. · Zbl 1306.68165
[60] Sharad Malik and Lintao Zhang. 2009. Boolean satisfiability from theoretical hardness to practical success. Communications of the ACM 52, 8 (Aug. 2009), 76–82. DOI:http://dx.doi.org/10.1145/1536616.1536637 · Zbl 05747903 · doi:10.1145/1536616.1536637
[61] Victor W. Marek and Mirosław Truszczyński. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-Year Perspective, Krzysztof R. Apt, Victor W. Marek, Mirosław Truszczyński, and David S. Warren (Eds.). Springer-Verlag, 375–398. DOI:http://dx.doi.org/10.1007/978-3-642-60085-2 · doi:10.1007/978-3-642-60085-2
[62] Wiktor Marek and Mirosław Truszczyński. 1991. Computing intersection of autoepistemic expansions. In Proceedings of the 1st International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’91), Anil Nerode, V. Wiktor Marek, and V. S. Subrahmanian (Eds.). MIT Press, 37–50.
[63] Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, Vol. 31. Oxford University Press, New York, NY. · Zbl 1095.68038 · doi:10.1093/acprof:oso/9780198566076.001.0001
[64] Ilkka Niemelä. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 3, 241–273. DOI:http://dx.doi.org/10.1023/A:1018930122475 · Zbl 0940.68018 · doi:10.1023/A:1018930122475
[65] Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. 2004. Detecting backdoor sets with respect to horn and binary clauses. In Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (SAT’04) (Lecture Notes in Computer Science), Holger H. Hoos and David G. Mitchell (Eds.), Vol. 3542. Springer-Verlag, 96–103.
[66] Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley. · Zbl 0833.68049
[67] Andreas Pfandler, Stefan Rümmele, and Stefan Szeider. 2013. Backdoors to abduction. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13), Francesca Rossi (Ed.). AAAI Press, 1046–1052.
[68] Patrik Simons, Ilkka Niemelä, and Timo Soininen. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 1–2, 181–234. DOI:http://dx.doi.org/10.1016/S0004-3702(02)00187-X · Zbl 0995.68021 · doi:10.1016/S0004-3702(02)00187-X
[69] Larry J. Stockmeyer and Albert R. Meyer. 1973. Word problems requiring exponential time. In Proceedings of the 5th Annual ACM Symposium on Theory of Computing (STOC’73), Alfred V. Aho, Allan Borodin, Robert L. Constable, Robert W. Floyd, Michael A. Harrison, Richard M. Karp, and H. Raymond Strong (Eds.). ACM, New York, 1–9. DOI:http://dx.doi.org/10.1145/800125.804029 · doi:10.1145/800125.804029
[70] Son Thanh To, Enrico Pontelli, and Tran Cao Son. 2009. A conformant planner with explicit disjunctive representation of belief states. In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS’09), Alfonso Gerevini, Adele E. Howe, Amedeo Cesta, and Ioannis Refanidis (Eds.). AAAI Press, 305–312.
[71] Mirosław Truszczyński. 2011. Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs. Theory and Practice of Logic Programming 11 (2011), 881–904. Issue 06. DOI:http://dx.doi.org/10.1017/S1471068410000463 · Zbl 1242.68052 · doi:10.1017/S1471068410000463
[72] G. S. Tseitin. 1968. On the complexity of derivation in propositional calculus. Zapiski Nauchnykh Seminarov Leningrad Otdelenie. Matematicheskiǐ Institut im. V. A. Steklova (LOMI) Akad. Nauk SSSR 8, 23–41. DOI:http://dx.doi.org/10.1007/978-3-642-81955-1_28 Russian. English translation in J. Siekmann and G. Wrightson (Eds.) Automation of Reasoning 2: Classical Papers on Computational Logic 1967–1970, Springer-Verlag, 466–483, 1983. · doi:10.1007/978-3-642-81955-1_28
[73] M. H. Van Emden and Robert. A. Kowalski. 1976. The semantics of predicate logic as a programming language. Journal of the ACM 23, 4 (October 1976), 733–742. DOI:http://dx.doi.org/10.1145/321978.321991 · Zbl 0339.68004 · doi:10.1145/321978.321991
[74] Moshe Y. Vardi. 2010. On P, NP, and computational complexity. Communications of the ACM 53, 11, 5. DOI:http://dx.doi.org/10.1145/1839676.1839677 · doi:10.1145/1839676.1839677
[75] Ryan Williams, Carla Gomes, and Bart Selman. 2003a. Backdoors to typical case complexity. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI’03), Georg Gottlob and Toby Walsh (Eds.). Morgan Kaufmann, 1173–1178.
[76] Ryan Williams, Carla Gomes, and Bart Selman. 2003b. On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In Informal Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT’03). 222–230.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.