×

zbMATH — the first resource for mathematics

Knowledge compilation of logic programs using approximation fixpoint theory. (English) Zbl 1379.68045
Summary: Recent advances in knowledge compilation introduced techniques to compile positive logic programs into propositional logic, essentially exploiting the constructive nature of the least fixpoint computation. This approach has several advantages over existing approaches: it maintains logical equivalence, does not require (expensive) loop-breaking preprocessing or the introduction of auxiliary variables, and significantly outperforms existing algorithms. Unfortunately, this technique is limited to negation-free programs. In this paper, we show how to extend it to general logic programs under the well-founded semantics.
We develop our work in approximation fixpoint theory, an algebraical framework that unifies semantics of different logics. As such, our algebraical results are also applicable to autoepistemic logic, default logic and abstract dialectical frameworks.

MSC:
68N17 Logic programming
68N20 Theory of compilers and interpreters
68Q55 Semantics in the theory of computing
68T27 Logic in artificial intelligence
Software:
ASSAT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abiteboul, S.; Vianu, V., Datalog extensions for database queries and updates, J. Comput. Syst. Sci., 43, 1, 62-124, (1991) · Zbl 0764.68158
[2] Antic, C.; Eiter, T.; Fink, M., pp., (2013)
[3] Asuncion, V.; Lin, F.; Zhang, Y.; Zhou, Y., Ordered completion for first-order logic programs on finite structures, Artif. Intell., 177-179, 1-24, (2012) · Zbl 1244.68072
[4] Ben-Eliyahu, R.; Dechter, R., Propositional semantics for disjunctive logic programs, Ann. Math. Artif. Intell., 12, 1-2, 53-87, (1994) · Zbl 0858.68012
[5] Bryant, R. E., Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, 35, 677-691, (1986) · Zbl 0593.94022
[6] Cadoli, M.; Donini, F. M., A survey on knowledge compilation, AI Commun., 10, 3-4, 137-150, (1997)
[7] Chavira, M.; Darwiche, A., pp., (2005)
[8] Chavira, M.; Darwiche, A., On probabilistic inference by weighted model counting, Artif. Intell., 172, 6-7, 772-799, (2008) · Zbl 1182.68297
[9] Darwiche, A., pp., (2011)
[10] Darwiche, A.; Marquis, P., A knowledge compilation map, J. Artif. Intell. Res. (JAIR), 17, 229-264, (2002) · Zbl 1045.68131
[11] Denecker, M.; Lierler, Y.; Truszczyński, M.; Vennekens, J., pp., (2012)
[12] Denecker, M.; Marek, V.; Truszczyński, M., Logic-Based Artificial Intelligence, Approximations, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning, 127-144, (2000), Springer · Zbl 0988.68183
[13] Denecker, M.; Marek, V.; Truszczyński, M., Ultimate approximation and its application in nonmonotonic knowledge representation systems, Information and Computation, 192, 1, 84-121, (2004) · Zbl 1074.68069
[14] Denecker, M.; Vennekens, J., pp., (2007)
[15] Denecker, M.; Vennekens, J., pp., (2014)
[16] Fierens, D.; Van den Broeck, G.; Renkens, J.; Shterionov, D. S.; Gutmann, B.; Thon, I.; Janssens, G.; De Raedt, L., Inference and learning in probabilistic logic programs using weighted Boolean formulas, TPLP, 15, 3, 358-401, (2015) · Zbl 1379.68062
[17] Fitting, M., Fixpoint semantics for logic programming – A survey, Theoretical Computer Science, 278, 1-2, 25-51, (2002) · Zbl 1002.68023
[18] Gelfond, M.; Lifschitz, V., pp., (1988)
[19] Huang, J.; Darwiche, A., pp., (2005)
[20] Janhunen, T., pp., (2004)
[21] Janhunen, T., Some (in)translatability results for normal logic programs and propositional theories, Journal of Applied Non-Classical Logics, 16, 1-2, 35-86, (2006) · Zbl 1184.68160
[22] Janhunen, T.; Niemelä, I.; Sevalnev, M.; Erdem, E.; Lin, F.; Schaub, T., LPNMR, Computing stable models via reductions to difference logic, 142-154, (2009), Springer · Zbl 1258.68030
[23] Kleene, S. C., On notation for ordinal numbers, The Journal of Symbolic Logic, 3, 4, 150-155, (1938) · Zbl 0020.33803
[24] Lifschitz, V.; Razborov, A. A., Why are there so many loop formulas?, ACM Trans. Comput. Log., 7, 2, 261-268, (2006) · Zbl 1367.68036
[25] Lin, F.; Zhao, J., pp., (2003)
[26] Lin, F.; Zhao, Y., ASSAT: computing answer sets of a logic program by SAT solvers, AIJ, 157, 1-2, 115-137, (2004) · Zbl 1085.68544
[27] Lowd, D.; Domingos, P., pp., (2008)
[28] Marek, V.; Truszczyński, M., The Logic Programming Paradigm: A 25-Year Perspective, Stable models and an alternative logic programming paradigm, 375-398, (1999), Springer-Verlag · Zbl 0979.68524
[29] Palacios, H.; Bonet, B.; Darwiche, A.; Geffner, H., pp., (2005)
[30] Pelov, N.; Denecker, M.; Bruynooghe, M., Well-founded and stable semantics of logic programs with aggregates, TPLP, 7, 3, 301-353, (2007) · Zbl 1111.68070
[31] Przymusinski, T. C., Foundations of Deductive Databases and Logic Programming, On the declarative semantics of deductive databases and logic programs, 193-216, (1988), Morgan Kaufmann · Zbl 0726.68067
[32] Selman, B.; Kautz, H. A., Knowledge compilation and theory approximation, J. ACM, 43, 2, 193-224, (1996) · Zbl 0882.68137
[33] Strass, H., Approximating operators and semantics for abstract dialectical frameworks, AIJ, 205, 39-70, (2013) · Zbl 1334.68212
[34] Suciu, D.; Olteanu, D.; Ré, C.; Koch, C., pp., (2011)
[35] Van den Broeck, G.; Darwiche, A., pp., (2015)
[36] van Emden, M. H.; Kowalski, R. A., The semantics of predicate logic as a programming language, J. ACM, 23, 4, 733-742, (1976) · Zbl 0339.68004
[37] Van Gelder, A.; Ross, K. A.; Schlipf, J. S., The well-founded semantics for general logic programs, J. ACM, 38, 3, 620-650, (1991) · Zbl 0799.68045
[38] Vlasselaer, J.; Van den Broeck, G.; Kimmig, A.; Meert, W.; De Raedt, L., pp., (2015)
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.