Intelligenza Artificiale - Volume 7, issue 1

Authors: Lenzerini, Maurizio | Schaerf, Marco

Article Type: Other

DOI: 10.3233/IA-130046

Citation: Intelligenza Artificiale, vol. 7, no. 1, pp. 1-5, 2013

Authors: Eiter, Thomas | Gottlob, Georg

Article Type: Research Article

Abstract: Marco Cadoli (5.12.1965 – 21.11.2006) was a well-known Italian Computer Scientist. This paper reviews his fundamental work in the area of nonmonotonic reasoning and also gives a very brief personal (and thus rather incomplete) account of his academic career and of his fruitful cooperation and interaction with the AI Group at TU Wien.

Keywords: Approximate reasoning, circumscription, computational complexity, knowledge compilation, nonmonotonic reasoning, problem solving, succinct representation

DOI: 10.3233/IA-130040

Citation: Intelligenza Artificiale, vol. 7, no. 1, pp. 7-17, 2013

Authors: Tinelli, Eufemia | Donini, Francesco M. | Di Sciascio, Eugenio

Article Type: Research Article

Abstract: We investigate on the possibility of transforming concepts in Description Logics into relational databases and queries in such a way that subsumption between the original concepts can be decided as query answering over a database. For the positive results, we show a translation of ${\cal ALN}$ -concepts into pairs (database, query) such that, in order to decide Subsumption $C \sqsubseteq D$ one evaluates the query resulting from the translation of D over the database resulting from C. For the negative results, we show that no compilation is possible for expressive Description Logics.

Keywords: Concept subsumption, description logics, RDBMS, SQL

DOI: 10.3233/IA-130044

Citation: Intelligenza Artificiale, vol. 7, no. 1, pp. 19-29, 2013

Authors: Liberatore, Paolo | Schaerf, Marco

Article Type: Research Article

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. Show more

DOI: 10.3233/IA-130041

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

Authors: Palopoli, Luigi | Schaerf, Andrea

Article Type: Research Article

Abstract: ${\sc np-spec}$ is a logic-based executable specification language developed primarily by Marco Cadoli, with the collaboration of these and other authors. This paper describes, by means of several examples, the core language of ${\sc np-spec}$ , along with its semantics and expressive power. Finally, we briefly discuss the translation of ${\sc np-spec}$ specifications into SAT formulae, which provides an efficient implementation of its execution engine.

Keywords: Specification languages, NP-complete problems, SAT solvers, executable specifications

DOI: 10.3233/IA-130043

Citation: Intelligenza Artificiale, vol. 7, no. 1, pp. 37-44, 2013

Authors: Greco, Gianluigi | Scarcello, Francesco

Article Type: Research Article

Abstract: In a great number of applications, it is necessary to distribute resources or tasks to agents collaborating with each other in order to maximize the social welfare of the structure they belong to. The question in these cases is how to divide in a fair way the outcome that the structure eventually earns, say money, to the participating agents. The paper faces this issue by focusing on a real-world application: the distribution of funds to Italian research structures and substructures, after a research assessment program (known as VQR) that is currently evaluating the Italian research production over years 2004–2010. A …number of desirable properties for any reasonable fair division rule are identified and exemplified for the case-study application. For instance, it is argued that the money distribution should be independent of possible alternative allocations of research products, and it should consider the actual contribution of every researcher to the outcome of the structure (s)he belongs to. Moreover, the whole process starting from the preliminary phase of products selection is dealt with, in order to prevent possible strategic behaviors from researchers that may lead their structure to miss its best possible score in the evaluation process. A fair solution based on the notion of Shapley value is described and analyzed. It turns out that the proposed solution enjoys all the desirable properties of fair division rules, and it could effectively be implemented in the VQR, as well as in related division-rules applications. Show more

Keywords: Social choice, coalitional game theory, mechanism design, Shapley value

DOI: 10.3233/IA-130042

Citation: Intelligenza Artificiale, vol. 7, no. 1, pp. 45-56, 2013

Authors: Cadoli, Marco | Calvanese, Diego | De Giacomo, Giuseppe | Mancini, Toni

Article Type: Research Article

Abstract: Finite model reasoning in UML class diagrams is an important task for assessing the quality of the analysis phase in the development of software applications in which it is assumed that the number of objects of the domain is finite. In this paper, we show how to encode finite model reasoning in UML class diagrams as a constraint satisfaction problem (CSP), exploiting techniques developed in description logics. In doing so we set up and solve an intermediate CSP problem to deal with the explosion of “class combinations” arising in the encoding. To solve the resulting CSP problems we rely on …the use of off-the-shelf tools for constraint modeling and programming. As a result, we obtain, to the best of our knowledge, the first implemented system that performs finite model reasoning on UML class diagrams. Show more

Keywords: UML class diagrams, description logics, constraint satisfaction problem, automated reasoning

DOI: 10.3233/IA-130045

Citation: Intelligenza Artificiale, vol. 7, no. 1, pp. 57-65, 2013