Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-16T09:24:18.619Z Has data issue: false hasContentIssue false
  • English
  • Français

Detection and exploitation of functional dependencies for model generation

Published online by Cambridge University Press:  25 September 2013

BROES DE CAT  and
MAURICE BRUYNOOGHE
BROES DE CAT
Affiliation:
Department of Computer Science, KU Leuven, Belgium (e-mail: [email protected], [email protected])
MAURICE BRUYNOOGHE
Affiliation:
Department of Computer Science, KU Leuven, Belgium (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Recent work in Answer Set Programming has integrated ideas from Constraint Programming. This has led to a new field called ASP Modulo CSP (CASP), in which the ASP language is enriched with constraint atoms representing constraint satisfaction problems. These constraints have a more compact grounding and are handled by a new generation of search algorithms. However, the burden is on the modeler to exploit these new constructs in his declarative problem specifications. Here, we explore how to remove this burden by automatically generating constraint atoms. We do so in the context of FO(·)IDP, a knowledge representation language that extends first-order logic with, among others, inductive definitions, arithmetic and aggregates. We uncover functional dependencies in declarative problem specifications with a theorem prover and exploit them with a transformation that introduces functions. Experimental evaluation shows that we obtain more compact groundings and better search performance.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 13 , Special Issue 4-5: 29th International Conference on Logic Programming , July 2013 , pp. 471 - 485
Copyright
Copyright © 2013 [BROES DE CAT and MAURICE BRUYNOOGHE] 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Apt, K. R. 2003. Principles of Constraint Programming. Cambridge University Press.CrossRefGoogle Scholar
Armstrong, W. W. 1974. Dependency structures of data base relationships. IFIP Congress, 580–580.Google Scholar
Balduccini, M. 2011. Industrial-size scheduling with asp+cp. In LPNMR, Delgrande, J. P. and Faber, W., Eds. Lecture Notes in Computer Science, vol. 6645. Springer, 284–296.Google Scholar
Balduccini, M. 2012. A “conservative” approach to extending answer set programming with non-herbrand functions. In Correct Reasoning, Erdem, E., Lee, J., Lierler, Y. and Pearce, D., Eds. Lecture Notes in Computer Science, vol. 7265. Springer Berlin Heidelberg, 24–39.CrossRefGoogle Scholar
Baral, C. 2003. Knowledge Representation, Reasoning, and Declarative Problem Solving. Cambridge University Press, New York, NY, USA.CrossRefGoogle Scholar
Bartholomew, M. and Lee, J. 2012. Stable models of formulas with intensional functions. See Brewka et al. (2012).Google Scholar
Baumgartner, P., Pelzer, B. and Tinelli, C. 2012. Model evolution with equality - revised and implemented. Journal of Symbolic Computation 47, 9, 1011–1045.CrossRefGoogle Scholar
Bogaerts, B., De Cat, B., De Pooter, S. and Denecker, M. 2012. IDP website. http://dtai.cs.kuleuven.be/krr/software/idp.Google Scholar
Brewka, G., Eiter, T. and McIlraith, S. A., Eds. 2012. Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10-14, 2012. AAAI Press.Google Scholar
Cabalar, P. 2011. Functional answer set programming. TPLP 11, 2–3, 203–233.Google Scholar
Cabalar, P. 2013. Setting the stage for asp functions. The Association for Logic Programming Newsletter 26, 2 (june).Google Scholar
Calimeri, F., Ianni, G. and Ricca, F. 2012. The third open answer set programming competition. CoRR abs/1206.3111.CrossRefGoogle Scholar
De Cat, B., Bogaerts, B., Devriendt, J. and Denecker, M. 2013. Model expansion in the presence of function symbols using constraint programming. Tech. Rep. CW 644, Departement of Computer Science, Katholieke Universiteit Leuven.Google Scholar
de Moura, L. M. and Bjørner, N. 2008. Z3: An efficient SMT solver. In TACAS, Ramakrishnan, C. R. and Rehof, J., Eds. LNCS, vol. 4963. Springer, 337–340.Google Scholar
Denecker, M. and Ternovska, E. 2008. A logic of nonmonotone inductive definitions. ACM Transactions on Computational Logic (TOCL) 9, 2 (Apr.), 14:1–52.CrossRefGoogle Scholar
Denecker, M., Vennekens, J., Bond, S., Gebser, M. and Truszczyński, M. 2009. The second answer set programming competition. In LPNMR. 637–654.CrossRefGoogle Scholar
Erdem, E., Lin, F. and Schaub, T., Eds. 2009. Logic Programming and Nonmonotonic Reasoning, 10th International Conference, LPNMR 2009, Potsdam, Germany, September 14-18, 2009. Proceedings, LNCS, vol. 5753. Springer.Google Scholar
Gebser, M., Ostrowski, M. and Schaub, T. 2009. Constraint answer set solving. In ICLP, Hill, P. M. and Warren, D. S., Eds. LNCS, vol. 5649. Springer, 235–249.Google Scholar
Janhunen, T., Niemelä, I. and Sevalnev, M. 2009. Computing stable models via reductions to difference logic. See Erdem et al. (2009), 142–154.Google Scholar
Lierler, Y. 2012. On the relation of constraint answer set programming languages and algorithms. In AAAI, Hoffmann, J. and Selman, B., Eds. AAAI Press.Google Scholar
Lifschitz, V. 2012. Logic programs with intensional functions. See Brewka et al. (2012).Google Scholar
Lin, F. and Wang, Y. 2008. Answer set programming with functions. In KR, Brewka, G. and Lang, J., Eds. AAAI Press, 454–465.Google Scholar
Marriott, K., Nethercote, N., Rafeh, R., Stuckey, P. J., de la Banda, M. G. and Wallace, M. 2008. The design of the Zinc modelling language. Constraints 13, 3, 229–267.CrossRefGoogle Scholar
Mears, C., de la Banda, M. J. G., Wallace, M. and Demoen, B. 2008. A novel approach for detecting symmetries in csp models. In CPAIOR, Perron, L. and Trick, M. A., Eds. Lecture Notes in Computer Science, vol. 5015. Springer, 158–172.Google Scholar
Niemelä, I. 2006. Answer set programming: A declarative approach to solving search problems. In JELIA. 15–18. Invited talk.CrossRefGoogle Scholar
Ostrowski, M. and Schaub, T. 2012. Asp modulo csp: The clingcon system. TPLP 12, 4–5, 485–503.Google Scholar
Pelov, N. 2004. Semantics of logic programs with aggregates. Ph.D. thesis, K.U.Leuven, Leuven, Belgium.Google Scholar
Pelov, N. and Ternovska, E. 2005. Reducing inductive definitions to propositional satisfiability. In ICLP, Gabbrielli, M. and Gupta, G., Eds. LNCS, vol. 3668. Springer, 221–234.Google Scholar
Rümmer, P. 2008. A constraint sequent calculus for first-order logic with linear integer arithmetic. In LPAR, Cervesato, I., Veith, H. and Voronkov, A., Eds. Lecture Notes in Computer Science, vol. 5330. Springer, 274–289.Google Scholar
Van Gelder, A. 1993. The alternating fixpoint of logic programs with negation. Journal of Computer and System Sciences 47, 1, 185–221.CrossRefGoogle Scholar
Weidenbach, C., Dimova, D., Fietzke, A., Kumar, R., Suda, M. and Wischnewski, P. 2009. Spass version 3.5. In CADE, Schmidt, R. A., Ed. Lecture Notes in Computer Science, vol. 5663. Springer, 140–145.Google Scholar
Wittocx, J., Denecker, M. and Bruynooghe, M. 2013. Constraint propagation for first-order logic and inductive definitions. ACM Transactions on Computational Logic. Accepted.CrossRefGoogle Scholar
Supplementary material: PDF

De Cat and Bruynooghe supplementary material

Appendix

Download De Cat and Bruynooghe supplementary material(PDF)
PDF 433.4 KB