Fundamenta Informaticae - Volume 159, issue 1-2

Authors: Maratea, Marco | Mascardi, Viviana | Ancona, Davide | Pettorossi, Alberto

Article Type: Other

DOI: 10.3233/FI-2018-1655

Citation: Fundamenta Informaticae, vol. 159, no. 1-2, pp. v-vi, 2018

Authors: Baldoni, Matteo | Baroglio, Cristina | Capuzzimati, Federico | Micalizio, Roberto

Article Type: Research Article

Abstract: We present the JaCaMo+ framework for programming multiagent systems (MAS), where agents interact thanks to commitment-based interaction protocols. Commitment protocols are realized as artifacts that maintain a social state and notify to the participating agents those events that are relevant to the interaction. We discuss the advantages, like increased modularity and flexibility, that are brought by commitment-ruled interactions with respect to other proposals. We trace back such advantages to the possibility of relying on a standardized commitment lifecycle. We explain how to use the framework to program interacting agents by using the Netbill protocol as running example, and the Gold …Miners scenario as a more complex programming example. Show more

Keywords: Interaction-Oriented Programming, Commitment-based protocols, JaCaMo

DOI: 10.3233/FI-2018-1656

Citation: Fundamenta Informaticae, vol. 159, no. 1-2, pp. 1-33, 2018

Authors: Chesani, Federico | Gavanelli, Marco | Lamma, Evelina | Mello, Paola | Montali, Marco

Article Type: Research Article

Abstract: The compliance verification task amounts to establishing if the execution of a system, given in terms of observed happened events, does respect a given property. In the past both the frameworks of Temporal Logics and Logic Programming have been extensively exploited to assess compliance in different domains, such as normative multi-agent systems, business process management and service oriented computing. In this work we review the LTL and SCIFF frameworks in the light of compliance evaluation, and formally investigate the relationship between the two approaches. We define a notion of compliance within each approach, and then we show that …an arbitrary LTL formula can be expressed in SCIFF, by providing a translation procedure from LTL to SCIFF which preserves compliance. Show more

Keywords: Linear Temporal Logic, Abductive Logic Programming, Compliance Verification

DOI: 10.3233/FI-2018-1657

Citation: Fundamenta Informaticae, vol. 159, no. 1-2, pp. 35-63, 2018

Authors: Gavanelli, Marco | Lamma, Evelina | Riguzzi, Fabrizio | Bellodi, Elena | Zese, Riccardo | Cota, Giuseppe

Article Type: Research Article

Abstract: Ontologies form the basis of the Semantic Web. Description Logics (DLs) are often the languages of choice for modeling ontologies. Integration of DLs with rules and rule-based reasoning is crucial in the so-called Semantic Web stack vision - a complete stack of recommendations and languages each based on and/or exploiting the underlying layers - which adds new features to the standards used in theWeb. The growing importance of the integration between DLs and rules is proved by the definition of the profile OWL 2 RL1 and the definition of languages such as RIF2 and SWRL3 …. Datalog± is an extension of Datalog which can be used for representing lightweight ontologies and expressing some languages of the DL-Lite family, with tractable query answering under certain language restrictions. In particular, it is able to express the DL-Lite version defined in OWL. In this work, we show that Abductive Logic Programming (ALP) can be used to represent Datalog± ontologies, supporting query answering through an abductive proof procedure, and smoothly achieving the integration of ontologies and rule-based reasoning. Often, reasoning with DLs means finding explanations for the truth of queries, that are useful when debugging ontologies and to understand answers given by the reasoning process. We show that reasoning under existential rules can be expressed by ALP languages and we present a solving system, which is experimentally proved to be competitive with DL reasoning systems. In particular, we consider an ALP framework named 𝒮CIFF derived from the IFF abductive framework. Forward and backward reasoning is naturally supported in this ALP framework. The 𝒮CIFF language smoothly supports the integration of rules, expressed in a Logic Programming language, with Datalog± ontologies, mapped into 𝒮CIFF (forward) integrity constraints. The main advantage is that this integration is achieved within a single language, grounded on abduction in computational logic, and able to model existential rules. Show more

DOI: 10.3233/FI-2018-1658

Citation: Fundamenta Informaticae, vol. 159, no. 1-2, pp. 65-93, 2018

Authors: Giordano, Laura | Gliozzi, Valentina | Olivetti, Nicola

Article Type: Research Article

Abstract: We explore the extension of the notion of rational closure to logics lacking the finite model property, considering the logic 𝒮𝒽𝒾𝓆. We provide a semantic characterization of rational closure in 𝒮𝒽𝒾𝓆 in terms of a preferential semantics, based on a finite rank characterization of minimal models. We show that the rational closure of a KB can be computed in EXP TIME based on a polynomial encoding of the rational extension of 𝒮𝒽𝒾𝓆 into entailment in 𝒮𝒽𝒾𝓆. We discuss the extension of rational closure to more expressive description logics.

Keywords: Description Logics, Nonmonotonic reasoning

DOI: 10.3233/FI-2018-1659

Citation: Fundamenta Informaticae, vol. 159, no. 1-2, pp. 95-122, 2018

Authors: Gottlob, Georg | Pieris, Andreas | Šimkus, Mantas

Article Type: Research Article

Abstract: It is realistic to assume that a database management system provides access to the active domain via built-in relations. Therefore, databases that include designated predicates that hold the active domain, which we call product databases, form a natural notion that deserves our attention. An important issue then is to look at the consequences of product databases for the expressiveness and complexity of central existential rule languages. We focus on guarded-based existential rules, and we investigate the impact of product databases on their expressive power and complexity. We show that the queries expressed via (frontier-)guarded rules gain in expressiveness, and in …fact, they have the same expressive power as Datalog. On the other hand, there is no impact on the expressiveness of the queries specified via weakly-(frontier-)guarded rules since they are powerful enough to explicitly compute the predicates needed to access the active domain. We also observe that there is no impact on the complexity of the query languages in question. Show more

Keywords: Rule-based languages, ontology-mediated queries, conjunctive queries, existential rules, tuple-generating dependencies, guardedness, expressive power, complexity

DOI: 10.3233/FI-2018-1660

Citation: Fundamenta Informaticae, vol. 159, no. 1-2, pp. 123-146, 2018

Authors: Lisi, Francesca A. | Mencar, Corrado

Article Type: Research Article

Abstract: We propose a method to extract and integrate fuzzy information granules from a populated OWL ontology. The purpose of this approach is to represent imprecise knowledge within an OWL ontology, as motivated by the fact that the Semantic Web is full of imprecise and uncertain information coming from perceptual data, incomplete data, data with errors, etc. In particular, we focus on Fuzzy Set Theory as a means for representing and processing information granules corresponding to imprecise concepts usually expressed by linguistic terms. The method applies to numerical data properties. The values of a property are first clustered to form a …collection of fuzzy sets. Then, for each fuzzy set, the relative σ-count is computed and compared with a number of predefined fuzzy quantifiers, which are therefore used to define new assertions that are added to the original ontology. In this way, the extended ontology provides both a punctual view and a granular view of individuals w.r.t. the selected property. We use a real-world ontology concerning hotels and populated with data of the Italian city of Pisa, to illustrate the method and to test its implementation. We show that it is possible to extract granular properties that can be described in natural language and smoothly integrated in the original ontology by means of annotated assertions. Show more

Keywords: Ontologies, OWL, Granular Computing, Fuzzy Set Theory

DOI: 10.3233/FI-2018-1661

Citation: Fundamenta Informaticae, vol. 159, no. 1-2, pp. 147-174, 2018

Authors: Malvone, Vadim | Murano, Aniello | Sorrentino, Loredana

Article Type: Research Article

Abstract: In game theory, deciding whether a designed player wins a game amounts to check whether he has a winning strategy. However, there are several game settings in which knowing whether he has more than a winning strategy is also important. For example, this is crucial in deciding whether a game admits a unique Nash Equilibrium, or in planning a rescue as this would provide a backup plan. In this paper we study the problem of checking whether, in a two-player reachability game, a designed player has more than a winning strategy. We investigate this question both under perfect …and imperfect information about the moves performed by the players. We provide an automata-based solution that results, in the perfect information setting, in a linear-time procedure; in the imperfect information setting, instead, it shows an exponential-time upper bound. In both cases, the results are tight. Show more

Keywords: Additional Strategies, Two-Player Reachability Games, Graded Modalities, Imperfect Information

DOI: 10.3233/FI-2018-1662

Citation: Fundamenta Informaticae, vol. 159, no. 1-2, pp. 175-195, 2018