Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-18T12:42:44.943Z Has data issue: false hasContentIssue false
  • English
  • Français

Programming in logic without logic programming

Published online by Cambridge University Press:  16 March 2016

ROBERT KOWALSKI  and
FARIBA SADRI
ROBERT KOWALSKI
Affiliation:
Department of Computing, Imperial College London, London, United Kingdom (e-mail: [email protected], [email protected])
FARIBA SADRI
Affiliation:
Department of Computing, Imperial College London, London, United Kingdom (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In previous work, we proposed a logic-based framework in which computation is the execution of actions in an attempt to make reactive rules of the form if antecedent then consequent true in a canonical model of a logic program determined by an initial state, sequence of events, and the resulting sequence of subsequent states. In this model-theoretic semantics, reactive rules are the driving force, and logic programs play only a supporting role. In the canonical model, states, actions, and other events are represented with timestamps. But in the operational semantics (OS), for the sake of efficiency, timestamps are omitted and only the current state is maintained. State transitions are performed reactively by executing actions to make the consequents of rules true whenever the antecedents become true. This OS is sound, but incomplete. It cannot make reactive rules true by preventing their antecedents from becoming true, or by proactively making their consequents true before their antecedents become true. In this paper, we characterize the notion of reactive model, and prove that the OS can generate all and only such models. In order to focus on the main issues, we omit the logic programming component of the framework.

Keywords

KELPSLPSModel generationReactive modelsState transition systems
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 16 , Special Issue 3: Special Issue on the International Web Rule Symposia 2012-2014 , May 2016 , pp. 269 - 295
Copyright
Copyright © Cambridge University Press 2016 

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

Abdennadher, S. and Schütz, H. 1998. CHR∨: A flexible query language. In Flexible Query Answering Systems, Andreasen, T., Christiansen, H. and Larsen, H., Eds. Springer, Berlin Heidelberg, 1–14.Google Scholar
Alberti, M., Chesani, F., Gavanelli, M., Lamma, E., Mello, P. and Torroni, P. 2008. Verifiable agent interaction in abductive logic programming: The SCIFF framework. ACM Transactions on Computational Logic (TOCL) 9 (4), 691–750.CrossRefGoogle Scholar
Alferes, J. J., Banti, F. and Brogi, A. 2006. An event-condition-action logic programming language. In Logics in Artificial Intelligence. JELIA 06, vol. 4160, Fisher, M., van der Hoek, W., Konev, B. and Lisitsa, A., Eds. LNIA, Springer, Berlin Heidelberg, 29–42.CrossRefGoogle Scholar
Bailey, J., Georgeff, M., Kemp, D., Kinny, D. and Ramamohanarao, K. 1995. Active databases and agent systems—a comparison. In Rules in Database Systems, Sellis, T., Ed. Springer, Berlin Heidelberg, 342–356.CrossRefGoogle Scholar
Baral, C. and Lobo, J. 1995. Characterizing production systems using logic programming and situation calculus. http://www.cs.utep.edu/baral/papers/char-prod-systems.ps.Google Scholar
Barringer, H., Fisher, M., Gabbay, D., Owens, R. and Reynolds, M. 1996. The Imperative Future: Principles of Executable Temporal Logic. John Wiley & Sons, Inc, New York, NY.Google Scholar
Betz, H. and Frühwirth, T. 2005. A linear-logic semantics for constraint handling rules. In Principles and Practice of Constraint Programming - CP 2005, vol. 3709, van Beek, P., Ed. LINCS, Springer, Berlin Heidelberg, 137–151.Google Scholar
Bonner, A. and Kifer, M. 1993. Transaction logic programming. In Proc. of the International Conference on Logic Programming, Warren, D. S., Ed. 257–279.Google Scholar
Brogi, A., Leite, J. A. and Pereira, L. M. 2002. Evolving logic programs. In Proc. of the 8th European Conference on Logics in Artificial Intelligence (JELIA'02), Flesca, S., Greco, S., Leone, N. and Ianni, G., Eds. Lecture Notes in Computer Science, vol. 2424. Springer-Verlag, Berlin, 50–61.Google Scholar
Calì, A., Gottlob, G. and Lukasiewicz, T. 2009. Datalog±: A unified approach to ontologies and integrity constraints. In Proc. of the 12th International Conference on Database Theory, Fagin, R., Ed. ACM, New York, NY, 14–30.CrossRefGoogle Scholar
Carriero, N. and Gelernter, D. 1989. Linda in context. Communications of the ACM 32 (4), 444–458.CrossRefGoogle Scholar
Costantini, S. and Tocchio, A. 2004. The DALI logic programming agent-oriented language. In Proc. of the JELIA 2004, Alferes, J. J. and Leite, J., Eds. Lecture Notes in Computer Science (LNAI), vol. 3229, Springer, Heidelberg, 685–688.Google Scholar
Damásio, C. V., Alferes, J. J. and Leite, J. 2010. Declarative semantics for the rule interchange format production rule dialect. In Proc. of Semantic Web–ISWC 2010, Patel-Schneider, P., Ed. Springer, Berlin Heidelberg, 798–813.CrossRefGoogle Scholar
Eiter, T., Feier, C. and Fink, M. 2012. Simulating production rules using ACTHEX. In Correct Reasoning, Erdem, E., Ed. LINCS, vol. 7265, Springer, Berlin Heidelberg, 211–228.CrossRefGoogle Scholar
Fernandes, A. A. A., Williams, M. H. and Paton, N. 1997. A logic-based integration of active and deductive databases. New Generation Computing 15 (2), 205–244.CrossRefGoogle Scholar
Fikes, R. E. and Nilsson, N. J. 1972. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 2 (3), 189–208.CrossRefGoogle Scholar
Frühwirth, T. 1998. Theory and practice of constraint handling rules. The Journal of Logic Programming 37 (1–3), 95–138.CrossRefGoogle Scholar
Frühwirth, T. 2009. Constraint Handling Rules. Cambridge University Press, Cambridge, UK.CrossRefGoogle Scholar
Fung, T. H. and Kowalski, R. 1997. The IFF proof procedure for abductive logic programming. The Journal of Logic Programming 33 (2), 151–165.CrossRefGoogle Scholar
Gavanelli, M., Lamma, E., Riguzzi, F., Bellodi, E., Zese, R. and Cota, G. 2015. Abductive logic programming for datalog± ontologies. In Proc. of the Technical Communications of the 31st International Conference on Logic Programming (ICLP 2015), De Vos, M., Eiter, T., Lierler, Y. and Toni, F., Eds. Vol. 1433, CEUR, ONLINE: http://ceur-ws.org/Vol-1433/.Google Scholar
Gebser, M., Grote, T., Kaminski, R. and Schaub, T. 2011. Reactive answer set programming. In Logic Programming and Nonmonotonic Reasoning, Delgrande, J. and Faber, W., Eds. LNAI, vol. 6645, Springer, Berlin, Heidelberg, 54–66.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In ICLP/SLP, vol. 88, 1070–1080.Google Scholar
Gomes, A. S. and Alferes, J. J. 2014. Transaction Logic with (Complex) Events.arXiv preprint arXiv:1405.3790.Google Scholar
Governatori, G. and Rotolo, A. 2013. Computing temporal defeasible logic. RuleML 2013, 114–128.Google Scholar
Gurevich, Y. 2000. Sequential abstract-state machines capture sequential algorithms. ACM Transactions on Computational Logic (TOCL) 1 (1), 77–111.CrossRefGoogle Scholar
Harel, D. 1987. Statecharts: A visual formalism for complex systems. Science of Computer Programming 8, 231–274.CrossRefGoogle Scholar
Jaffar, J. and Lassez, J. L. 1987. Constraint logic programming. In Proc. of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, ACM, New York NY, 111–119.CrossRefGoogle Scholar
Kakas, A. C., Kowalski, R. and Toni, F. 1998. The role of logic programming in abduction. In Handbook of Logic in Artificial Intelligence and Programming, Vol. 5, Gabbay, D., Hogger, C. J. and Robinson, J. A., Eds. Oxford University Press, Oxford, 235–324.Google Scholar
Kakas, A. C., Mancarella, P., Sadri, F., Stathis, K. and Toni, F. 2004. The KGP model of agency. In Proc. ECAI-2004.Google Scholar
Kowalski, R. 2011. Computational Logic and Human Thinking: How to be Artificially Intelligent. Cambridge University Press, Cambridge, UK.CrossRefGoogle Scholar
Kowalski, R. 2014. Logic for Problem Solving, Revisited. Frühwirth, Thom, Ed., Herstellung und Verlag, Books on Demand GmbH, Norderstedt.Google Scholar
Kowalski, R. and Sadri, F. 1999. From logic programming towards multi-agent systems. Annals of Mathematics and Artificial Intelligence 25, 391–419.CrossRefGoogle Scholar
Kowalski, R. and Sadri, F. 2009. Integrating logic programming and production systems in abductive logic programming agents. In Proc. of the 3rd International Conference on Web Reasoning and Rule Systems, Polleres, A. and Swift, T., Eds. LNCS, vol. 5837, Springer, Berlin Heidelberg, 1–23.Google Scholar
Kowalski, R. and Sadri, F. 2010. An agent language with destructive assignment and model-theoretic semantics. In Proc. of the 11th International Workshop on Computational Logic in Multi-Agent Systems (CLIMA), Dix, J., Leite, J., Governatori, G. and Jamroga, W., Eds. LNAI, vol. 6245, Springer, Berlin Heidelberg, 200–218.Google Scholar
Kowalski, R. and Sadri, F. 2011. Abductive logic programming agents with destructive databases. Annals of Mathematics and Artificial Intelligence 62 (1), 129–158 Cambridge, UK.CrossRefGoogle Scholar
Kowalski, R. and Sadri, F. 2012. A logic-based framework for reactive systems. In Rules on the Web: Research and Applications, 2012 – RuleML 2012, vol. 7438, Bikakis, A. and Giurca, A., Eds. Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1–15.Google Scholar
Kowalski, R. and Sadri, F. 2014. A logical characterization of a reactive system language. In RuleML 2014, vol. 8620, Bikakis, A. et al., Eds. RuleML 2014, Lecture Notes in Computer Science, Springer International Publishing, Switzerland, 22–36 Google Scholar
Kowalski, R. and Sadri, F. 2015. Model-theoretic and operational semantics for reactive computing. New Generation Computing 33 (1), 33–67.CrossRefGoogle Scholar
Kowalski, R. and Sergot, M. 1986. A logic-based calculus of events. New Generation Computing 4 (1), 67–95.CrossRefGoogle Scholar
Lausen, G., Ludäscher, B. and May, W. 1998. On active deductive databases: The statelog approach. In Proc. of the Transactions and Change in Logic Databases, Decker, H., Freitag, B., Kifer, M. and Voronkov, A., Eds. LNCS, vol. 1472, Springer, Berlin Heidelberg, 69–106.CrossRefGoogle Scholar
Maier, D., Mendelzon, A. and Sagiv, Y. 1979. Testing implications of data dependencies. ACM Transactions on Database Systems 4 (4), 455–469.CrossRefGoogle Scholar
Mancarella, P., Terreni, G., Sadri, F., Toni, F. and Endriss, U. 2009. The CIFF proof procedure for abductive logic programming with constraints: Theory, implementation and experiments. Theory and Practice of Logic Programming 9 (06), 691–750.CrossRefGoogle Scholar
Manthey, R. and Bry, F. 1988. January. SATCHMO: A theorem prover implemented in prolog. In Proc. of the Conference on Automated Deduction, LNCS, vol. 310, Lusk, E. and Overbeek, R., Eds. Springer, Berlin Heidelberg, 415–434.CrossRefGoogle Scholar
Paschke, A., Boley, H., Zhao, Z., Teymourian, K. and Athan, T. 2012. Reaction RuleML 1.0: Standardized semantic reaction rules. In Rules on the Web: Research and Applications, Bikakis, A. and A. Eds. LNCS, vol. 7438, Springer, Berlin Heidelberg, 100–119.CrossRefGoogle Scholar
Rao, A. S. and Georgeff, M. P. 1995. BDI agents: From theory to practice. In Proc. of the International Conference on Multiagent Systems - ICMAS, Lesser, V. and Gasser, L., Eds. The MIT Press, Cambridge, MA, 312–319.Google Scholar
Rao, A. 1996. AgentSpeak (L): BDI agents speak out in a logical computable language. In Agents Breaking Away, 42–55.Google Scholar
Raschid, L. 1994. A semantics for a class of stratified production system programs. The Journal of Logic Programming 21 (1), 31–57.CrossRefGoogle Scholar
Rezk, M. and Kifer, M. 2012. Formalizing production systems with rule-based ontologies. In Foundations of Information and Knowledge Systems, Lukasiewicz, T. and Sali, A., Eds. LNCS, vol. 7153, Springer, Berlin Heidelberg, 332–351.CrossRefGoogle Scholar
Shanahan, M. 1997. Solving the Frame Problem: A Mathematical Investigation of the Common Sense Law of Inertia. MIT Press, Cambridge, MA and London, England.Google Scholar
Shapiro, E. (1989). The family of concurrent logic programming languages. ACM Computing Surveys (CSUR) 21 (3), 413–510.CrossRefGoogle Scholar
Thielscher, M. 2005. FLUX: A logic programming method for reasoning agents. Theory and Practice of Logic Programming 5 (4–5), 533–565.CrossRefGoogle Scholar
Van Gelder, A., Ross, K. A. and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. Journal of the ACM (JACM) 38 (3), 619–649.CrossRefGoogle Scholar
Wang, J., Topor, R. and Maher, M. 2001. Reasoning with disjunctive constrained tuple-generating dependencies. In Database and Expert Systems Applications, Mayr, H., Lazansky, J., Quirchmayr, G. and Vogel, P., Eds. LNCS, vol. 2113, Springer, Berlin Heidelberg, 963–973 CrossRefGoogle Scholar
Zaniolo, C. 1993. On the unification of active databases and deductive databases. In Advances in Databases, Worboys, M. and Grundy, A., Eds. LNCS, Springer, Berlin Heidelberg, 23–39.CrossRefGoogle Scholar
Supplementary material: PDF

Kowalski and Sadri supplementary material

Appendix

Download Kowalski and Sadri supplementary material(PDF)
PDF 94.7 KB