Abstract
This paper is concerned with an abstraction for SLD-refutation. In most studies on abstraction, any goal is proved with a fixed abstraction neglecting differences of goals. On the other hand, we propose a new framework of Goal-Dependent Abstraction in which an appropriate abstraction can be selected according to each goal to be proved. Towards Goal-Dependent Abstraction, this paper tries to construct an appropriate abstraction for a given goal. The appropriateness is defined in terms of Upward-Property and Downward-Property. Our abstraction is based on predicate mapping. Given a goal, candidate predicate mappings are generated and tested in their appropriateness. To find appropriate abstractions efficiently, we present a property to reduce the computational cost of candidate generation. The numbers of pruned candidates are evaluated in both of the best and worst cases. Some experimental results show that many useless candidates can be pruned with the property and constructed abstractions fit our intuition.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
David A. Plaisted, “Theorem Proving with Abstraction”, Artificial Intelligence, vol. 16, 47–108, 1981.
Josh D. Tenenberg, “Abstracting First-Order Theories”, Change of Representation and Inductive Bias (D. Paul Benjamin ed.), Kluwer Academic Publishers, pp. 67–79, 1989.
Josh D. Tenenberg, “Abstraction in Planning”, Reasoning about Plans (James F. Allen et al.), Morgan Kaufmann Publishers, pp. 213–283, 1991.
Craig A. Knoblock, “Automatically Generating Abstractions for Problem Solving”, Technical Report CMU-CS-91-120, School of Computer Science, Carnegie Mellon University, 1991.
Fusto Giunchiglia and Toby Walsh, “A Theory of Abstraction”, Artificial Intelligence, vol. 57, pp. 323–389, 1992.
Y. Okubo and M. Haraguchi, “Planning with Abstraction Based on Partial Predicate Mappings”, Proc. of the Third Workshop on Algorithmic Learning Theory, pp. 183–194, 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Okubo, Y., Haraguchi, M. (1994). Constructing predicate mappings for Goal-Dependent Abstraction. In: Arikawa, S., Jantke, K.P. (eds) Algorithmic Learning Theory. AII ALT 1994 1994. Lecture Notes in Computer Science, vol 872. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58520-6_87
Download citation
DOI: https://doi.org/10.1007/3-540-58520-6_87
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58520-6
Online ISBN: 978-3-540-49030-2
eBook Packages: Springer Book Archive