Reasoning with limited resources: active logics expressed as labelled deductive systems

• Autorzy: Asker M. , Malec J.
• Języki publikacji: EN

Abstrakty

EN

Reasoning with limited computational resources (such as time or memory) is an important problem, in particular in knowledge-intensive embedded systems. Classical logic is usually considered inappropriate for this purpose as no guarantees regarding deadlines can be made. One of the more interesting approaches to address this problem is built around the concept of active logics. Although a step in the right direction, active logics are just a preliminary attempt towards finding an acceptable solution. Our work is based on the assumption that labelled deductive systems (LDSs) offer appropriate metamathematical methodology to study the problem. As a first step, we have reformulated a pair of active logics systems, namely the memory model and its formalized simplification, the step logic, as LDSs. This paper presents our motivation behind this project, followed by an overview of the investigations on meta-reasoning relevant to this work, and introduces in some reasonable detail the MM system.

Słowa kluczowe

EN

active logic; labelled deductive systems; reasoning with limited resources

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2005
• Tom: Vol. 53, nr 1
• Strony: 69--78
• Opis fizyczny: Bibliogr. 27 poz., 2 rys.

Twórcy

autor

Asker M.

autor

Malec J.

• Department of Computer Science, Lund University, Box 118 221 00 Lund, Sweden.,

Bibliografia

• [1] B. Selman and H. Kautz, “Knowledge compilation and theory approximation”, JACM 43(2), 193–224 (1996).
• [2] D. Gabbay, Labelled Deductive Systems, Vol. 1, Oxford University Press, 1996.
• [3] J. Elgot-Drapkin, Step Logic: Reasoning Situated in Time, PhD Thesis, Department of Computer Science, University of Maryland, 1988.
• [4] J. Elgot-Drapkin, S. Kraus, M. Miller, M. Nirkhe, and D. Perlis, “Active logics: A unified formal approach to episodic reasoning. Technical report”, Department of Computer Science, University of Maryland, 1996.
• [5] K. Purang, D. Purushothaman, D. Traum, C. Andersen, D. Traum, and D. Perlis, “Practical reasoning and plan execution with active logic”. in: Proceedings of the IJCAI’ 99 Workshop on Practical Reasoning and Rationality, 1999.
• [6] J. Elgot-Drapkin, “Step-logic and the three-wise-men problem”, in: Proc. AAAI, 412–417 (1991).
• [7] M. Nirkhe, S. Kraus, and D. Perlis, “Situated reasoning within tight deadlines and realistic space and computation bounds”, in: Proc. Common Sense 93, 1993.
• [8] H.-D. Ebbinghaus, “Is there a logic for polynomial time?”, L.J. of the IGPL 7(3), 359–374 (1999).
• [9] G. De Giacomo, L. Iochhi, D. Nardi, and R. Rosati, “A theory and implementation of cognitive mobile robots”, J. Logic Computation 9(5), 759–785 (1999).
• [10] P.F. Patel-Schneider, “A decidable first-order logic for knowledge representation”, in: Proc. IJCAI 85, 455–458 (1985).
• [11] P.F. Patel-Schneider, “A four-valued semantics for framebased description languages”, in: Proc. AAAI 86, 344–348 (1986).
• [12] M. Cadoli and F. Donini, “A survey on knowledge compilation”, AI Communications, 2001.
• [13] M. Cadoli and M. Schaerf, “Approximate reasoning and non-omniscient agents”, in: Proc. TARK 92, 169–183 (1992).
• [14] G. Gogic, C. Papadimitriou, and M. Sideri, “Incremental recompilation of knowledge”, JAIR 8, 23–37 (1998).
• [15] H. Levesque, “A logic of implicit and explicit belief”, in: Proc. AAAI 84, 198–202, 1984.
• [16] R. Fagin, J.Y. Halpern, Y. Moses, and M.Y. Vardi, Reasoning about Knowledge, MIT Press, 2003.
• [17] T. Ågotnes, A Logic of Finite Syntactic Epistemic States, PhD thesis, Department of Informatics, University of Bergen, Norway, 2004.
• [18] W. van der Hoek and M. Wooldridge, “Cooperation, knowledge and time: Alternating-time temporal epistemic logic and its applications”, Studia Logica 75, 125–157 (2003).
• [19] J. Grant, S. Kraus, and D. Perlis, “A logic for character- Bull. Pol. Ac.: Tech. 53(1) 2005 77 M. Asker and J. Malecizing multiple bounded agents”, Autonomous Agents and Multi-Agent Systems 3(4), 455–458 (2000).
• [20] D. Gabbay and J. Woods, “The new logic”, L.J. of the IGPL 9(2), 141–174 (2001).
• [21] M. Wooldridge and A. Lomuscio, “A computationally grounded logic of visibility, perception, and knowledge”, L. J. of the IGPL 9(2), 257–272 (2001).
• [22] J. Drapkin, M. Miller, and D. Perlis, “A memory model for real-time commonsense reasoning”, Technical Report TR-86-21, Department of Computer Science, University of Maryland, 1986.
• [23] M. Asker and J. Malec, “Reasoning with limited resources: An LDS-based approach”, B. Tessem et al, eds. in: Proc. Eight Scandinavian Conference on Artificial Intelligence 13–24, IOS Press, 2003.
• [24] M. Nirkhe, Time-Situated Reasoning Within Tight Deadlines and Realistic Space and Computation Bounds, PhD thesis, Department of Computer Science, University of Maryland, 1994.
• [25] A. Globerman, “A modal active logic with focus of attention for reasoning in time”, Master’s thesis, Department of Mathematics and Computer Science, Bar-Illan University, 1997.
• [26] M. Asker, “Logical reasoning with temporal constraints”, Master’s thesis, Department of Computer Science, Lund University, August 2003. Available at http://ai.cs.lth.se/xj/MikaelAsker/exjobb0820.ps.
• [27] M. Lin and J. Malec, “Timing analysis of RL programs”, Control Engineering Practice 6, 403–408 (1998).