×

zbMATH — the first resource for mathematics

Expressiveness of logic programs under the general stable model semantics. (English) Zbl 1367.68044
MSC:
68N17 Logic programming
68T27 Logic in artificial intelligence
Software:
ASSAT; Cmodels; Datalog
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. Ajtai. 1983. Σ11-formulae on finite structures. Ann. Pure Appl. Logic 24 (1983), 1–48. · Zbl 0519.03021 · doi:10.1016/0168-0072(83)90038-6
[2] M. Ajtai and Y. Gurevich. 1994. Datalog vs first-order logic. J. Comput. Syst. Sci. 49 (1994), 562–588. · Zbl 0824.68034 · doi:10.1016/S0022-0000(05)80071-6
[3] V. Asuncion, F. Lin, Y. Zhang, and Y. Zhou. 2012. Ordered completion for first-order logic programs on finite structures. Artif. Intell. 177–179 (2012), 1–24. · Zbl 1244.68072
[4] R. Ben-Eliyahu and R. Dechter. 1994. Propositional semantics for disjunctive logic programs. Ann. Math. Artif. Intell. 12, 1–2 (1994), 53–87. · Zbl 0858.68012
[5] Y. Chen, F. Lin, Y. Wang, and M. Zhang. 2006. First-order loop formulas for normal logic programs. In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning. 298–307.
[6] Y. Chen, F. Lin, Y. Zhang, and Y. Zhou. 2011. Loop-separable programs and their first-order definability. Artif. Intell. 175 (2011), 890–913. · Zbl 1223.68027 · doi:10.1016/j.artint.2010.12.001
[7] E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. 2001. Complexity and expressive power of logic programming. Comput. Surv. 33, 3 (2001), 374–425. · doi:10.1145/502807.502810
[8] A. Durand, E. Grandjean, and F. Olive. 2004. New results on arity vs. number of variables. Research Report 20–2004, LIF, Marseille, France (2004).
[9] A. Durand, C. Lautemann, and T. Schwentick. 1998. Subclasses of binary NP. J. Logic Comput. 8, 2 (1998), 189–207. · Zbl 0901.68076 · doi:10.1093/logcom/8.2.189
[10] H.-D. Ebbinghaus and J. Flum. 1999. Finite Model Theory (2nd ed.). Springer-Verlag, New York. · Zbl 0932.03032
[11] Thomas Eiter, Michael Fink, Jörg Pührer, Hans Tompits, and Stefan Woltran. 2013. Model-based recasting in answer-set programming. J. Appl. Non-Class. Logics 23, 1–2 (2013), 75–104.
[12] Thomas Eiter, Michael Fink, Hans Tompits, and Stefan Woltran. 2004. On eliminating disjunctions in stable logic programming. In Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning. 447–458. · Zbl 1122.68369
[13] T. Eiter and G. Gottlob. 1997. Expressiveness of stable model semantics for disjunctive logic programs with functions. J. Logic Program. 33 (1997), 167–178. · Zbl 0890.68030 · doi:10.1016/S0743-1066(97)00027-7
[14] T. Eiter, G. Gottlob, and Y. Gurevich. 1996. Normal forms for second-order logic over finite structures, and classication of NP optimization problems. Ann. Pure Appl. Logic 78 (1996), 111–125. · Zbl 0883.03015 · doi:10.1016/0168-0072(95)00033-X
[15] T. Eiter, G. Gottlob, and H. Mannila. 1997. Disjunctive datalog. ACM Trans. Database Syst. 22 (1997), 364–418. Issue 3.
[16] R. Fagin. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation (SIAM-AMS Proceedings), Vol. 7. 43–73. · Zbl 0303.68035
[17] P. Ferraris, J. Lee, and V. Lifschitz. 2011. Stable models and circumscription. Artif. Intell. 175 (2011), 236–263. · Zbl 1227.68103 · doi:10.1016/j.artint.2010.04.011
[18] P. Ferraris, J. Lee, V. Lifschitz, and R. Palla. 2009. Symmetric splitting in the general theory of stable models. In Proceedings of the 21st International Joint Conference on Artificial Intelligence. 797–803.
[19] M. Gelfond and V. Lifschitz. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference and Symposium on Logic Programming. 1070–1080.
[20] Etienne Grandjean. 1985. Universal quantifiers and time complexity of random access machines. Math. Syst. Theory 18, 2 (1985), 171–187. · Zbl 0578.03022 · doi:10.1007/BF01699468
[21] Neil Immerman. 1999. Descriptive Complexity. Springer. · Zbl 0918.68031 · doi:10.1007/978-1-4612-0539-5
[22] Tomi Janhunen. 2006. Some (in)translatability results for normal logic programs and propositional theories. J. Appl. Non-Classic. Logics 16, 1–2 (2006), 35–86. · Zbl 1184.68160
[23] J. Lee and Y. Meng. 2011. First-order stable model semantics and first-order loop formulas. J. Artif. Intell. Res. 42 (2011), 125–180. · Zbl 1234.68247
[24] D. Leivant. 1989. Descriptive characterizations of computational complexity. J. Comput. Syst. Sci. 39 (1989), 51–83. · Zbl 0677.68045 · doi:10.1016/0022-0000(89)90019-6
[25] Yuliya Lierler and Marco Maratea. 2004. Cmodels-2: SAT-based answer set solver enhanced to non-tight programs. In Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning. 346–350. · Zbl 1122.68377
[26] F. Lin and Y. Zhao. 2004. ASSAT: Computing answer sets of a logic program by SAT solvers. Artif. Intell. 157, 1–2 (2004), 115–137. · Zbl 1085.68544
[27] F. Lin and Y. Zhou. 2011. From answer set logic programming to circumscription via logic of GK. Artif. Intell. 175, 1 (2011), 264–277. · Zbl 1216.68270 · doi:10.1016/j.artint.2010.04.001
[28] J. Lobo, J. Minker, and A. Rajasekar. 1992. Foundations of Disjunctive Logic Programming. The MIT Press, Cambridge. · Zbl 0755.68033
[29] David Pearce and Agustín Valverde. 2005. A first order nonmonotonic extension of constructive logic. Stud. Logic. 80, 2/3 (2005), 321–346. · Zbl 1097.03020 · doi:10.1007/s11225-005-8473-8
[30] J. S. Schlipf. 1995. The expressive powers of the logic programming semantics. J. Comput. Syst. Sci. 51, 1 (1995), 64–86. · Zbl 0831.68012 · doi:10.1006/jcss.1995.1053
[31] L. J. Stockmeyer. 1977. The polynomial-time hierarchy. Theoret. Comput. Sci. 3 (1977), 1–22. · Zbl 0353.02024 · doi:10.1016/0304-3975(76)90061-X
[32] Heng Zhang and Yan Zhang. 2013a. Disjunctive logic programs versus normal logic programs. CoRR abs/1304.0620, http://arxiv.org/abs/1304.0620. · Zbl 1314.68100
[33] Heng Zhang and Yan Zhang. 2013b. First-order expressibility and boundedness of disjunctive logic programs. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 1198–1204.
[34] Heng Zhang, Yan Zhang, Mingsheng Ying, and Yi Zhou. 2011. Translating first-order theories into logic programs. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence. 1126–1131.
[35] Yi Zhou. 2015. First-order disjunctive logic programming vs normal logic programming. In Proceedings of the 24th International Joint Conference on Artificial Intelligence. 3292–3298.
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.