NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Abstraction and Problem ReformulationIn work done jointly with Toby Walsh, the author has provided a sound theoretical foundation to the process of reasoning with abstraction (GW90c, GWS9, GW9Ob, GW90a). The notion of abstraction formalized in this work can be informally described as: (property 1), the process of mapping a representation of a problem, called (following historical convention (Sac74)) the 'ground' representation, onto a new representation, called the 'abstract' representation, which, (property 2) helps deal with the problem in the original search space by preserving certain desirable properties and (property 3) is simpler to handle as it is constructed from the ground representation by "throwing away details". One desirable property preserved by an abstraction is provability; often there is a relationship between provability in the ground representation and provability in the abstract representation. Another can be deduction or, possibly inconsistency. By 'throwing away details' we usually mean that the problem is described in a language with a smaller search space (for instance a propositional language or a language without variables) in which formulae of the abstract representation are obtained from the formulae of the ground representation by the use of some terminating rewriting technique. Often we require that the use of abstraction results in more efficient .reasoning. However, it might simply increase the number of facts asserted (eg. by allowing, in practice, the exploration of deeper search spaces or by implementing some form of learning). Among all abstractions, three very important classes have been identified. They relate the set of facts provable in the ground space to those provable in the abstract space. We call: TI abstractions all those abstractions where the abstractions of all the provable facts of the ground space are provable in the abstract space; TD abstractions all those abstractions wllere the 'unabstractions' of all the provable facts of the abstract space are provable in the ground space; and TC abstractions all those abstractions where a fact is provable in the ground space if and only if its abstraction is provable in the abstract space.
Document ID
19960047152
Acquisition Source
Ames Research Center
Document Type
Conference Paper
Authors
Giunchiglia, Fausto
(Trento Univ. Povo, Italy)
Date Acquired
September 6, 2013
Publication Date
April 1, 1992
Publication Information
Publication: Proceedings of the Workshop on Change of Representation and Problem Reformulation
Subject Category
Cybernetics
Accession Number
96N32914
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
No Preview Available