Sub-Program . This part of the program consists of a single, non-ground rule that guesses
that is, Hguesses a truth assignment for some variable A and stores it in relation v
. We
that is, Bextracts the truth assignment from relation v
into the variables X as described
X (resp. Y). If the rule is satisfied, Brsat(X,Y,1) should hold, and Brsat(X,Y,0) otherwise. This
Sub-Program 1. This part of the program needs to check that, given the guess
made in
, there exists at least one answer set of the epistemic reduct
, as per Definition 3(1).
Fig. 1: Creating a grid from chains.
alternative way to show the lower bound for ELP consistency, but relies on the existence
Fig. 2: Benchmark results. Missing points indicate timeouts.
available at http://www.qbflib.org/family_detail.php?idFamily=56, split-
ABSEHER, M., MUSLIU, N., AND WOLTRAN, S. 2017. htd - A free, open-source framework for (cus-
tomized) tree decompositions and beyond. In Proc. CPAIOR. 376–386. ALVIANO, M., DODARO, C., FABER, W., LEONE, N., AND RICCA, F. 2013. WASP: A native ASP solver
based on constraint learning. In Proc. LPNMR. 54–66. BICHLER, M., MORAK, M., AND WOLTRAN, S. 2016a. lpopt: A rule optimization tool for answer set
programming. In Proc. LOPSTR. 114–130. BICHLER, M., MORAK, M., AND WOLTRAN, S. 2016b. The power of non-ground rules in answer set
programming. TPLP 16, 5-6, 552–569. BICHLER, M., MORAK, M., AND WOLTRAN, S. 2018a. Single-shot epistemic logic program solving. In
Proc. IJCAI. 1714–1720. BICHLER, M., MORAK, M., AND WOLTRAN, S. 2018b. Single-shot epistemic logic program solving. In
Proc. ASPOCP. BLIEM, B., MOLDOVAN, M., MORAK, M., AND WOLTRAN, S. 2017. The impact of treewidth on ASP
grounding and solving. In Proc. IJCAI. 852–858. BODLAENDER, H. L. 1993. A tourist guide through treewidth. Acta Cybern. 11, 1-2, 1–21. BREWKA, G., EITER, T., AND TRUSZCZYNSKI, M. 2011. Answer set programming at a glance. Commun.
ACM 54, 12, 92–103. CALIMERI, F., FUSCÀ, D., PERRI, S., AND ZANGARI, J. 2017. I-DLV: the new intelligent grounder of
DEL CERRO, L. F., HERZIG, A., AND SU, E. I. 2015. Epistemic equilibrium logic. In Proc. IJCAI. 2964–2970.
EBBINGHAUS, H.-D. AND FLUM, J. 1995. Finite Model Theory. Springer Monographs in Mathematics. Springer, Berlin, Heidelberg.
EITER, T., FABER, W., FINK, M., AND WOLTRAN, S. 2007. Complexity results for answer set programming with bounded predicate arities and implications. Ann. Math. Artif. Intell. 51, 2-4, 123–165.
EITER, T. AND GOTTLOB, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Ann. Math. Artif. Intell. 15, 3-4, 289–323.
FABER, W., MORAK, M., AND WOLTRAN, S. 2019. Strong equivalence for epistemic logic programs made easy. In Proc. AAAI.
FABER, W., PFEIFER, G., AND LEONE, N. 2011. Semantics and complexity of recursive aggregates in answer set programming. Artif. Intell. 175, 1, 278–298.
FERRARIS, P., LEE, J., AND LIFSCHITZ, V. 2011. Stable models and circumscription. Artif. Intell. 175, 1, 236–263.
GEBSER, M., KAMINSKI, R., KAUFMANN, B., AND SCHAUB, T. 2012. Answer Set Solving in Practice. Morgan & Claypool.
GEBSER, M., KAMINSKI, R., KAUFMANN, B., AND SCHAUB, T. 2014. clingo = ASP + control: Preliminary report. In ICLP Tech.Comm.
GEBSER, M., KAMINSKI, R., KAUFMANN, B., AND SCHAUB, T. 2019. Multi-shot ASP solving with clingo. TPLP 19, 1, 27–82.
GEBSER, M., KAMINSKI, R., KÖNIG, A., AND SCHAUB, T. 2011. Advances in gringo series 3. In Proc. LPNMR. 345–351.
GEBSER, M., KAUFMANN, B., AND SCHAUB, T. 2009. Solution enumeration for projected boolean search problems. In Proc. CPAIOR. 71–86.
GEBSER, M., KAUFMANN, B., AND SCHAUB, T. 2012. Conflict-driven answer set solving: From theory to practice. Artif. Intell. 187, 52–89.
GELFOND, M. 1994. Logic programming and reasoning with incomplete information. Ann. Math. Artif. Intell. 12, 1-2, 89–116.
GELFOND, M. AND LIFSCHITZ, V. 1988. The stable model semantics for logic programming. In Proc. ICLP/SLP. 1070–1080.
GELFOND, M. AND LIFSCHITZ, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9, 3/4, 365–386.
KAHL, P. T. 2014. Refining the semantics for epistemic logic programs. Ph.D. thesis, Texas Tech University, Texas, USA.
KAHL, P. T., LECLERC, A. P., AND SON, T. C. 2016. A parallel memory-efficient epistemic logic program solver: Harder, better, faster. In Proc. ASPOCP.
KAHL, P. T., WATSON, R., BALAI, E., GELFOND, M., AND ZHANG, Y. 2015. The language of epistemic specifications (refined) including a prototype solver. J. Log. Comput., exv065.
LECLERC, A. P. AND KAHL, P. T. 2018. A survey of advances in epistemic logic program solvers. CoRR abs/1809.07141.
LIFSCHITZ, V., TANG, L. R., AND TURNER, H. 1999. Nested expressions in logic programs. Ann. Math. Artif. Intell. 25, 3-4, 369–389.
MORAK, M. AND WOLTRAN, S. 2012. Preprocessing of complex non-ground rules in answer set programming. In ICLP Tech.Comm. 247–258.
PELOV, N., DENECKER, M., AND BRUYNOOGHE, M. 2007. Well-founded and stable semantics of logic programs with aggregates. TPLP 7, 3, 301–353.
PULINA, L. 2016. The ninth QBF solvers evaluation - preliminary report. In Proc. QBF. CEUR Workshop Proceedings, vol. 1719. CEUR-WS.org, 1–13.
SHEN, Y. AND EITER, T. 2016. Evaluating epistemic negation in answer set programming. Artif. Intell. 237, 115–135.
SHEN, Y., WANG, K., EITER, T., FINK, M., REDL, C., KRENNWALLNER, T., AND DENG, J. 2014. FLP answer set semantics without circular justifications for general logic programs. Artif. Intell. 213, 1–41.
SON, T. C., LE, T., KAHL, P. T., AND LECLERC, A. P. 2017. On computing world views of epistemic logic programs. In Proc. IJCAI. 1269–1275.
TRUSZCZYNSKI, M. 2011. Revisiting epistemic specifications. In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning - Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday. 315–333.
ZHANG, Z., WANG, B., AND ZHANG, S. 2015. Logic programming with graded introspection. In Proc. ASPOCP.