The compilability framework

Issue title: The scientific legacy of Marco Cadoli in Artificial Intelligence

Article type: Research Article

Authors: Liberatore, Paolo | Schaerf, Marco

Affiliations: Department of Computer, Management and Automation Engineering, Sapienza University of Rome, Rome, Italy

Note: [] Corresponding author: P. Liberatore, Department of Computer, Management and Automation Engineering, Sapienza University of Rome, Via Ariosto 25, 00185, Rome, Italy. E-mail: paolo@liberatore.org

Abstract: Several problems in AI can be structured in two parts based on the nature of their data, being it fixed or varying. As an example, in automated planning an instance is made of the actions that can be performed and the specific initial state and goal; given a domain of application, the actions will stay the same, while over time planning may be required to be performed several time with differing initial and final states. The compilability classes formalize the complexity of such problems, and can also be used to establish the relative size of certain data structures and the space efficiency of knowledge representation formalisms. In this paper we review the compilability framework and its applications in various areas of Artificial Intelligence.

DOI: 10.3233/IA-130041

Journal: Intelligenza Artificiale, vol. 7, no. 1, pp. 31-35, 2013