Model-Checking Memory Requirements of Resource-Bounded Reasoners

Alex Albore, Natasha Alechina, Piergiorgio Bertoli, Chiara Ghidini, Brian Logan, Luciano Serafini

Memory bounds may limit the ability of a reasoner to make inferences and therefore affect the reasoner's usefulness. In this paper, we propose a framework to automatically verify the reasoning capabilities of propositional memory-bounded reasoners which have a sequential architecture. Our framework explicitly accounts for the use of memory both to store facts and to support backtracking in the course of deductions. We describe an implementation of our framework in which proof existence is recast as a strong planning problem, and present results of experiments using the MBP planner which indicate that memory bounds may not be trivial to infer even for simple problems, and that memory bounds and length of derivations are closely interrelated.

Subjects: 3. Automated Reasoning; 9. Foundational Issues

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.