[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Reactive Computing as Model Generation

  • Published:
New Generation Computing Aims and scope Submit manuscript

Abstract

In this paper we propose a logic-based, framework inspired by artificial intelligence, but scaled down for practical database and programming applications. Computation in the framework is viewed as the task of generating a sequence of state transitions, with the purpose of making an agent’s goals all true. States are represented by sets of atomic sentences (or facts), representing the values of program variables, tuples in a coordination language, facts in relational databases, or Herbrand models.

In the model-theoretic semantics, the entire sequence of states and events are combined into a single model-theoretic structure, by associating timestamps with facts and events. But in the operational semantics, facts are updated destructively, without timestamps. We show that the model generated by destructive updates is identical to the model generated by reasoning with facts containing timestamps. We also extend the model with intentional predicates and composite event predicates defined by logic programs containing conditions in first-order logic, which query the current state.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Abiteboul, S., Hull, R. and Vianu, V., Foundations of Databases, Addison-Wesley, 1995.

  2. Agotnes, T., Van Der Hoek, W., Rodriguez-Aguilar, J. A., Sierra, C., and Wooldridge, M. “On the logic of normative systems,” Proc. of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI’07), pp. 1181–1186, 2007.

  3. Alferes, J.J., Banti, F. and Brogi A., “An Event-Condition-Action Logic Programming Language,” 10th European Conference on Logics in Artificial Intelligence. JELIA 06, Lecture Notes in Artificial Intelligence 4160, Springer-Verlag, pp. 29–42, 2006.

  4. Bailey, J., Georgeff, M., Kemp, D., Kinny, D. and Ramamohanarao, K., “Active databases and agent systems—A comparison,” Rules in Database Systems, pp. 342–356, 1995.

  5. Baral, C. and Lobo, J., “Characterizing production systems using logic programming and situation calculus” http://www.cs.utep.edu/baral/papers/char-prod-systems.ps, 1995.

  6. Bonner, A. and Kifer, M., “Transaction logic programming,” in Logic Programming: Proc. of the 10th International Conf (Warren D. S., Ed.), pp. 257–279, 1993.

  7. Brogi, A., Leite, J. A. and Pereira, L. M., “Evolving Logic Programs,” in 8th European Conference on Logics in Artificial Intelligence (JELIA’02) (S. Flesca, S. Greco, N. Leone, G. Ianni Eds.), LNCS 2424, Springer-Verlag, pp. 50–61, 2002.

  8. Calì, A., Gottlob, G., and Lukasiewicz, T., “Datalog±: a unified approach to ontologies and integrity constraints,” Proc. of the 12th International Conference on Database Theory, pp. 14–30, ACM, 2009.

  9. Carriero, N. and Gelernter, D., “Linda in Context,” Communications of the ACM, 32(4), 1989.

  10. Costantini, S. and Tocchio, A., “The DALI Logic Programming Agent-Oriented Language,” in JELIA 2004. LNCS (LNAI), Vol. 3229 (Alferes, J.J., Leite, J. Eds.), Springer, Heidelberg, pp. 685–688, 2004.

  11. Damásio, C., Alferes, J. and Leite, J., “Declarative semantics for the rule interchange format production rule dialect,” The Semantic Web–ISWC 2010, pp. 798–813, 2010.

  12. Dovier, A., Formisano, A. and Pontelli, E., “Autonomous agents coordination: Action languages meet CLP(FD) and Linda,” Theory and Practice of Logic Programming, 2012.

  13. Eiter, T., Subrahmanian, V.S. and G Pick, G., “Heterogeneous active agents, I,” AI Journal, 108(1–2), pp. 179–255, 1999.

  14. Eiter, T., Feier, C., and Fink, M., “Simulating production rules using ACTHEX,” Correct Reasoning, pp. 211–228, 2012.

  15. Fernandes, A.A.A., Williams, M.H., and Paton, N., “A Logic-Based Integration of Active and Deductive Databases,” New Generation Computing, 15(2), pp. 205–244, 1997.

  16. Fikes, R. E. and Nilsson, N. J., “STRIPS: A new approach to the application of theorem proving to problem solving,” Artificial intelligence, 2(3), pp.189–208, 1972.

  17. Fisher, M., “A Survey of Concurrent METATEM - The Language and its Applications,” Lecture notes in computer science, 827, Springer Verlag pp. 480–505, 1994.

  18. Gelfond, M. and Lifschitz, V., “The stable model semantics for logic programming,” in Proceedings of the 5th International Conference on Logic programming, pp. 1070–1080, 1988.

  19. Gurevich, Y., “Evolving algebras 1993: Lipari guide,” Specification and validation methods, pp. 9–36, 1995.

  20. Harel, D., “Statecharts: A Visual Formalism for Complex Systems,” Sci. Comput. Programming 8, pp. 231–274, 1987.

  21. Hausmann, S., Scherr, M. and Bry, F., “Complex Actions for Event Processing,” Research Report, Institute for Informatics, University of Munich, 2012.

  22. Hellerstein, J.M., “The Declarative Imperative: Experiences and Conjectures in Distributed Logic,” SIGMOD Record 39(1), 2010.

  23. Kakas, A. C., Kowalski, R. and Toni, F., “The Role of Logic Programming in Abduction,” Handbook of Logic in Artificial Intelligence and Programming 5, Oxford University Press, pp. 235–324, 1998.

  24. Kakas, A. C., Mancarella, P., Sadri, F., Stathis, K, and Toni, F., “The KGP model of agency,” in Proc. ECAI-2004, 2004.

  25. Khandelwal A., Fox P.: “General Descriptions of Additive Effects via Aggregates in the Circumscriptive Event Calculus,” Technical Report, Computer Science. Rensselaer Polytechnic Institute, New York (2012)

    Google Scholar 

  26. Knuth, D. E., The Art of Computer Programming. Vol. 1: Fundamental Algorithms, Addison-Wesley, 1973.

  27. Kowalski, R., “Predicate logic as programming language,” in IFIP Congress, Vol. 74, pp. 569–544, 1974.

  28. Kowalski, R. and Sadri, F., “From Logic Programming Towards Multi-agent Systems,” Annals of Mathematics and Artificial Intelligence, Vol 25, pp. 391–419, 1999.

  29. Kowalski, R. and Sadri, F., “Integrating Logic Programming and Production Systems in Abductive Logic Programming Agents,” in Proceedings of The Third International Conference on Web Reasoning and Rule Systems, Chantilly, Virginia, USA, 2009.

  30. Kowalski, R. and Sadri, F., “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., Jamroga W. (Eds.), pp. 200–218, 2010.

  31. Kowalski, R. and Sadri, F., “Abductive Logic Programming Agents with Destructive Databases,” Annals of Mathematics and Artificial Intelligence, 62(1), pp. 129–158, 2011.

  32. Kowalski, R. and Sadri, F., “A Logic-Based Framework for Reactive Systems,” in Rules on the Web: Research and Applications, 2012 (A. Bikakis and A. Giurca Eds.), LNCS 7438, Springer-Verlag, pp. 1–15, 2012.

  33. Kowalski, R. and Sergot, M., “A Logic-based Calculus of Events,” in New Generation Computing, 4(1), pp. 67-95, 1986.

  34. Lausen, G., Ludäscher, B. and May, W., “On Active Deductive Databases: The Statelog Approach,” Transactions and Change in Logic Databases (Decker, H., Freitag B., Kifer, M., Voronkov, A. Eds.), LNCS 1472, Springer, 1998.

  35. Levesque, H. J., Reiter, R., Lesperance, Y., Lin, F. and Scherl, R. B., “GOLOG: A logic programming language for dynamic domains,” The Journal of Logic Programming, 31(1), pp. 59–83, 1997.

  36. Lloyd, J.W. and Topor, R.W., “Making PROLOG More Expressive,” Journal of Logic Programming 1(3), pp. 225–240, 1984.

  37. Loo, B. T., Condie, B. T., Garofalakis, M., Gay, D. E., Hellerstein, J. M., Maniatis, P., Ramakrishnan, R., Roscoe, T., and Stoica, I., “Declarative Networking,” in Communications of the ACM (CACM), 2009.

  38. Mancarella, P., Terreni, G., Sadri, F., Toni, F. and Endriss, U., “The CIFF Proof Procedure for Abductive Logic Programming with Constraints: Theory, Implementation and Experiments,” Theory and Practice of Logic Programming, 2009.

  39. Manna, Z. and Pnueli, A., The temporal logic of reactive and concurrent systems: specifications. Vol. 1., Springer, 1992.

  40. McCarthy, J. and Hayes, P., “Some Philosophical Problems from the Standpoint of Artificial Intelligence,” Machine Intelligence 4, Edinburgh University Press. pp. 463–502, 1969.

  41. Miller R. and Shanahan, M., “Some Alternative Formulations of the Event Calculus,” Computational logic: logic programming and beyond, Springer-Verlag, pp. 452–490, 2002.

  42. Nicolas J.M., Gallaire H.: “Database: Theory vs. Interpretation” in Logic and Databases (Gallaire, H., Minker, J. Eds.). Plenum, New York (1978)

    Google Scholar 

  43. Przymusinski, T., “On the declarative semantics of stratified deductive databases and logic programs,” Foundations of Deductive Databases and Logic Programming (Morgan Kaufmann, J. Minker Ed.), pp. 193–216, 1987.

  44. Rao, A., “AgentSpeak (L): BDI agents speak out in a logical computable language,” Agents Breaking Away, pp. 42–55, 1996.

  45. Rao, A. S. and Georgeff, M. P., “BDI Agents: From Theory to Practice,” International Conference on Multiagent Systems - ICMAS, pp. 312–319, 1995.

  46. Raschid, L., “A Semantics for a Class of Stratified Production System Programs,” J. Log. Program. 21(1), pp. 31–57, 1994.

  47. Reisig, W., “The Expressive Power of Abstract-State Machines,” Computing and Informatics, Vol. 22, pp. 209–219, 2003.

  48. Rezk, M. and Kifer, M., “Formalizing production systems with rule-based ontologies,” Foundations of Information and Knowledge Systems, pp. 332–351, 2012.

  49. Shanahan, M., Solving the frame problem: a mathematical investigation of the common sense law of inertia, MIT Press, 1997.

  50. Thielscher, M., “FLUX: A logic programming method for reasoning agents,” Theory and Practice of Logic Programming, 5(4-5), pp. 533–565, 2005.

  51. Turner, H., “Non-monotonic Causal Logic,” in Foundations of Artificial Intelligence Vol. 3, (Frank van Harmelen, Vladimir Lifschitz and Bruce Porter Eds.), Elsevier, pp. 759–776, 2008.

  52. Van Gelder, A., Ross, K. A., and Schlipf, J. S., “The well-founded semantics for general logic programs,” Journal of the ACM (JACM), 38(3), pp. 619–649, 1991.

  53. Zaniolo, C., “On the Unification of Active Databases and Deductive databases,” in 11th British National Conference on Databases, pp. 23–39, 1993.

  54. Kowalski, R. and Sadri, F., “Completeness of a Reactive System Language,” Department of Computing, Imperial College London, 2014.

Download references

Author information

Authors and Affiliations

  1. Imperial College London, London, United Kingdom

    Robert Kowalski & Fariba Sadri

Authors
  1. Robert Kowalski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fariba Sadri
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Robert Kowalski.

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kowalski, R., Sadri, F. Reactive Computing as Model Generation. New Gener. Comput. 33, 33–67 (2015). https://doi.org/10.1007/s00354-015-0103-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00354-015-0103-z

Keywords

Search

Navigation