Reactive computing as model generation.

*(English)*Zbl 1333.68108Summary: 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.

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.

##### MSC:

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

03B70 | Logic in computer science |

68N17 | Logic programming |

68P15 | Database theory |

68Q55 | Semantics in the theory of computing |

68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |

##### Keywords:

state transition systems; reactive systems; composite event processing; model generation; frame problem
PDF
BibTeX
XML
Cite

\textit{R. Kowalski} and \textit{F. Sadri}, New Generation Comput. 33, No. 1, 33--67 (2015; Zbl 1333.68108)

Full Text:
DOI

##### References:

[1] | Abiteboul, S., Hull, R. and Vianu, V., Foundations of Databases, Addison-Wesley, 1995. · Zbl 0848.68031 |

[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. · Zbl 1152.68397 |

[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. · Zbl 1014.68534 |

[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. · Zbl 0806.68015 |

[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. · Zbl 1110.68499 |

[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. · Zbl 1267.68079 |

[13] | Eiter, T., Subrahmanian, V.S. and G Pick, G., “Heterogeneous active agents, I,” AI Journal, 108(1-2), pp. 179-255, 1999. · Zbl 0914.68123 |

[14] | Eiter, T., Feier, C., and Fink, M., “Simulating production rules using ACTHEX,” Correct Reasoning, pp. 211-228, 2012. · Zbl 1357.68217 |

[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. · Zbl 0234.68036 |

[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. · Zbl 0949.68532 |

[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. · Zbl 0852.68053 |

[20] | Harel, D., “Statecharts: A Visual Formalism for Complex Systems,” Sci. Comput. Programming 8, pp. 231-274, 1987. · Zbl 0637.68010 |

[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. · Zbl 1182.68279 |

[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) |

[26] | Knuth, D. E., The Art of Computer Programming. Vol. 1: Fundamental Algorithms, Addison-Wesley, 1973. · Zbl 0191.17903 |

[27] | Kowalski, R., “Predicate logic as programming language,” in IFIP Congress, Vol. 74, pp. 569-544, 1974. · Zbl 0297.68006 |

[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. · Zbl 0940.68017 |

[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. · Zbl 1286.68417 |

[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. · Zbl 1230.68200 |

[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. · Zbl 1356.68221 |

[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. · Zbl 0903.68066 |

[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. · Zbl 0880.68008 |

[36] | Lloyd, J.W. and Topor, R.W., “Making PROLOG More Expressive,” Journal of Logic Programming 1(3), pp. 225-240, 1984. · Zbl 0584.68022 |

[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. · Zbl 1184.68161 |

[39] | Manna, Z. and Pnueli, A., The temporal logic of reactive and concurrent systems: specifications. Vol. 1., Springer, 1992. · Zbl 0753.68003 |

[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. · Zbl 0226.68044 |

[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. · Zbl 1012.68192 |

[42] | Nicolas, J.M.; Gallaire, H.; Gallaire, H. (ed.); Minker, J. (ed.), “database: theory vs. interpretation”, (1978), New York |

[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. · Zbl 0811.68094 |

[47] | Reisig, W., “The Expressive Power of Abstract-State Machines,” Computing and Informatics, Vol. 22, pp. 209-219, 2003. · Zbl 1104.68507 |

[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. · Zbl 1105.68333 |

[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. · Zbl 0799.68045 |

[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. |

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.