Abstract
We investigate the application of Courcelle’s theorem and the logspace version of Elberfeld et al. in the context of non-monotonic reasoning. Here we formalize the implication problem for propositional sets of formulas, the extension existence problem for default logic, the expansion existence problem for autoepistemic logic, the circumscriptive inference problem, as well as the abduction problem in monadic second order logic and thereby obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu, resp., XLnu) under standard complexity assumptions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Beyersdorff O., Meier A., Thomas M., Vollmer H.: The complexity of propositional implication. Inf. Process. Lett. 109(18), 1071–1077 (2009). doi:10.1016/j.ipl.2009.06.015
Beyersdorff, O., Meier, A., Thomas, M., Vollmer, H.: The complexity of reasoning for fragments of default logic. J. Logic Comput. 22(3), 587–604 (2012). doi:10.1093/logcom/exq061
Bodlaender H.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1–45 (1998)
Brewka G., Niemelä I., Truszczynski M.: Nonmonotonic Reasoning. Elsevier, Amsterdam (2008)
Buntrock G., Damm C., Hertrampf U., Meinel C.: Structure and importance of logspace mod-classes. Math. Syst. Theory 25, 223–237 (1992)
Cadoli, M., Lenzerini, M.: The complexity of closed world reasoning and circumscription. In: Proceedings of 8th National Conference on Artificial Intelligence, pp. 550–555. AAAI Press (1990)
Chen, Y., Flum, J., Grohe, M.: Bounded nondeterminism and alternation in parameterized complexity theory. In: Proceedings of the 18th IEEE Annual Conference on Computational Complexity (CCC 2003), pp. 13–29 (2003). doi:10.1109/CCC.2003.1214407
Courcelle B., Engelfriet J.: Graph Structure and Monadic Second-Order Logic, A Language Theoretic Approach. Cambridge University Press, Cambridge (2012)
Creignou, N., Meier, A., Thomas, M., Vollmer, H.: The complexity of reasoning for fragments of autoepistemic logic. ACM Trans. Comput. Logic 13(2) (2010)
Creignou, N., Schmidt, J., Thomas, M.: Complexity of propositional abduction for restricted sets of boolean functions. In: Proceedings of 12th International Conference on the Principles of Knowledge Representation and Reasoning. AAAI Press (2010)
Eiter T., Gottlob G.: Propositional circumscription and extended closed-world reasoning are \({\Pi_{2}^{P}}\)-complete. Theor. Comput. Sci. 114(2), 231–245 (1993)
Eiter T., Gottlob G.: The complexity of logic-based abduction. JACM 42(1), 3–42 (1995)
Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: Proceedings of 51th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society (2010)
Elberfeld, M., Stockhusen, C., Tantau, T.: On the space complexity of parameterized problems. In: Parameterized and Exact Computation, pp. 206–217. Springer, Berlin (2012)
Fellows, M. R., Pfandler, A., Rosamond, F. A., Rümmele, S.: The parameterized complexity of abduction. In: Proceedings of 26th AAAI Conference on Artificial Intelligence (2012)
Flum J., Grohe M.: Parameterized Complexity Theory. Springer, Berlin (2006)
Gelfond M., Przymusinska H., Przymusinski T.C.: On the relationship between circumscription and negation as failure. Artif. Intell. 38(1), 75–94 (1989)
Gottlob G.: Complexity results for nonmonotonic logics. J. Logic Comput. 2(3), 397–425 (1992)
Gottlob G., Pichler R., Wei F.: Bounded treewidth as a key to tractability of knowledge representation and reasoning. Artif. Intell. 174(1), 105–132 (2010)
Gottlob G., Scarcello F., Sideri M.: Fixed-parameter complexity in ai and nonmonotonic reasoning. Artif. Intell. 138(1), 55–86 (2002)
Gottlob G., Szeider S.: Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems. Comput. J. 51(3), 303–325 (2008)
Jakl, M., Pichler, R., Woltran, S.: Answer-Set Programming with Bounded Treewidth. In: Proceedings of 21st IJCAI, pp. 816–822 (2009)
Kirousis L.M., Kolaitis P.G.: The complexity of minimal satisfiability problems. Inf. Comput. 187(1), 20–39 (2003)
Lifschitz, V.: Computing circumscription. In: Proceedings of 9th International Joint Conference on Artificial Intelligence, pp. 121–127. Morgan Kaufman (1985)
Marek V., Truszczynski M.: Nonmonotonic Logic: Context-Dependent Reasoning. Springer, Berlin (1993)
Marek, V., Truszczynski, M.: Stable models and an alternative logic programming paradigm. In: The Logic Programming Paradigm—A 25-Year Perspective, pp. 375–398 (1999)
McCarthy J.: Circumscription—a form of non-monotonic reasoning. Artif. Intell. 13(1–2), 27–39 (1980)
Moore R.C.: Semantical considerations on modal logic. Artif. Intell. 25, 75–94 (1985)
Niemelä, I.: Towards automatic autoepistemic reasoning. In: Proceedings of 2nd European Workshop on Logics in Artificial Intelligence, LNCS, vol. 478, pp. 428–443. Springer, Berlin (1990)
Niemelä I.: Logic programming with stable model semantics as a constraint programming paradigm. Ann. Math. Artif. Intell. 25(3–4), 241–273 (1999)
Nordh, G.: A trichotomy in the complexity of propositional circumscription. In: Proceedings of 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, pp. 257–269. Springer, Berlin (2004)
Peirce C.S.: Philosophical Writings of Peirce. Courier Dover Publications, New York (1955)
Peirce C.S., Hartshorne C., Weiss P.: The Collected Papers of Charles Sanders Peirce. Cambridge Press, Cambridge (1932)
Post E.: The two-valued iterative systems of mathematical logic. Ann. Math. Stud. 5, 1–122 (1941)
Reiter R.: A logic for default reasoning. Artif. Intell. 13, 81–132 (1980)
Thomas, M.: On the complexity of fragments of nonmonotonic logics. Ph.D. thesis, Leibniz Universität Hannover (2010)
Thomas M., Vollmer H.: Complexity of non-monotonic logic. Bull. EATCS 102, 53–82 (2010)
Zaho X., Ding D.: Fixed-parameter tractability of disjunction-free default reasoning. JCST 18(1), 118–124 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported in part by DFG Grant VO 630/6-2 and ME 4279/1-1. Part of this work has been published in a preliminary form in: A. Meier and J. Schmidt and M. Thomas and H. Vollmer, On the Parameterized Complexity of Default Logic and Autoepistemic Logic, Proc. LATA 2012, pp. 389–400, vol. 7183 LNCS.
Rights and permissions
About this article
Cite this article
Meier, A., Schindler, I., Schmidt, J. et al. On the parameterized complexity of non-monotonic logics. Arch. Math. Logic 54, 685–710 (2015). https://doi.org/10.1007/s00153-015-0435-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-015-0435-x