Piero A. Bonatti

IJCAI Conference 2023 Conference Paper

A False Sense of Security (Extended Abstract)

• Piero A. Bonatti

The growing literature on confidentiality in knowledge representation and reasoning sometimes may cause a false sense of security, due to lack of details about the attacker, and some misconceptions about security-related concepts. This paper analyzes the vulnerabilities of some recent knowledge protection methods to increase the awareness about their actual effectiveness and their mutual differences.

IJCAI Conference 2023 Conference Paper

Optimizing the Computation of Overriding in DLN (Extended Abstract)

• Piero A. Bonatti
• Iliana Petrova
• Luigi Sauro

One of the factors that hinder the adoption of nonmonotonic description logics in applications is performance. Even when monotonic and nonmonotonic inferences have the same asymptotic complexity, the implementation of nonmonotonic reasoning may be significantly slower. The family of nonmonotonic logics DLN is no exception to this behavior. We address this issue by introducing two provably correct and complete optimizations for reasoning in DLN. The first optimization is a module extractor that has the purpose of focusing reasoning on a relevant subset of the knowledge base. The second, called optimistic evaluation, aims at exploiting incremental reasoning in a better way. Extensive experimental evaluation shows that the optimized DLN reasoning is often compatible with interactive query answering, thus bringing nonmonotonic description logics closer to practical applications.

AIJ Journal 2022 Journal Article

A false sense of security

• Piero A. Bonatti

The growing literature on confidentiality in knowledge representation and reasoning sometimes may cause a false sense of security, due to lack of details about the attacker, and some misconceptions about security-related concepts. This note analyzes the vulnerabilities of some recent knowledge protection methods to increase the awareness about their actual effectiveness and their mutual differences.

KR Conference 2022 Conference Paper

Sticky Policies in OWL2: Extending PL with Fixpoints and Transitive Closure

• Piero A. Bonatti
• Luigi Sauro

PL is a low-complexity profile of OWL2, expressly designed to encode data usage policies and personal data protection regulations - such as the GDPR - in a machine understandable way. With PL, the compliance of privacy policies with the GDPR and with the data subjects' consent to processing can be checked automatically and in real time. In this paper, we extend PL to support "sticky policies". They are a sort of license that applies to data transfers, and specifies how the recipient can use the data. Sticky policies may be "recursive", i. e. they may apply not only to the first data transfer, but also to all subsequent transfer operations that the (direct or indirect) recipients may execute in the future. Such recursive sticky policies may be encoded with fixpoints or transitive role closure. In this paper we prove that such extensions make compliance checking intractable. Since the scalability of compliance checking is a major requirement in this area, these results justify a specialized, low complexity approach to encoding sticky policies.

IJCAI Conference 2020 Conference Paper

Rational Closure For All Description Logics (Extended Abstract)

• Piero A. Bonatti

Many modern applications of description logics (DLs, for short), such as biomedical ontologies and semantic web policies, provide compelling motivations for extending DLs with an overriding mechanism analogous to the homonymous feature of object-oriented programming. Rational closure (RC) is one of the candidate semantics for such extensions, and one of the most intensively studied. So far, however, it has been limited to strict fragments of SROIQ(D) – the logic on which OWL2 is founded. In this paper we prove that RC cannot be extended to logics that do not satisfy the disjoint model union property, including SROIQ(D). Then we introduce a refinement of RC called stable rational closure that overcomes the dependency on the disjoint model union property. Our results show that stable RC is a natural extension of RC. However, its positive features come at a price: stable RC re-introduces one of the undesirable features of other nonmonotonic logics, namely, deductive closures may not exist and may not be unique.

AIJ Journal 2020 Journal Article

Real-time reasoning in OWL2 for GDPR compliance

• Piero A. Bonatti
• Luca Ioffredo
• Iliana M. Petrova
• Luigi Sauro
• Ida R. Siahaan

This paper shows how knowledge representation and reasoning techniques can be used to support organizations in complying with the GDPR, that is, the new European data protection regulation. This work is carried out in a European H2020 project called SPECIAL. Data usage policies, the consent of data subjects, and selected fragments of the GDPR are encoded in a fragment of OWL2 called PL (policy language); compliance checking and policy validation are reduced to subsumption checking and concept consistency checking. This work proposes a satisfactory tradeoff between the expressiveness requirements on PL posed by the modeling of the GDPR, and the scalability requirements that arise from the use cases provided by SPECIAL's industrial partners. Real-time compliance checking is achieved by means of a specialized reasoner, called PLR, that leverages knowledge compilation and structural subsumption techniques. The performance of a prototype implementation of PLR is analyzed through systematic experiments, and compared with the performance of other important reasoners. Moreover, we show how PL and PLR can be extended to support richer ontologies, by means of import-by-query techniques. We prove novel tractability and intractability results related to PL, and some negative results about the restrictions posed on ontology import.

IJCAI Conference 2018 Conference Paper

Fast Compliance Checking in an OWL2 Fragment

• Piero A. Bonatti

We illustrate a formalization of data usage policies in a fragment of OWL2. It can be used to encode (i) a company's data protection policy, (ii) data subjects' consent to data processing, and (iii) part of the GDPR (the forthcoming European Data Protection Regulation). Then a company's policy can be checked for compliance with data subjects' consent and with part of the GDPR by means of subsumption queries. We provide a complete and tractable structural subsumption algorithm for compliance checking and prove the intractability of a natural generalization of the policy language.

IJCAI Conference 2018 Conference Paper

On the Logical Properties of the Description Logic DL^N (Extended abstract)

• Piero A. Bonatti
• Luigi Sauro

DL^N is a recent nonmonotonic description logic, designed for satisfying independently proposed knowledge engineering requirements, and for removing some recurrent drawbacks of traditional nonmonotonic semantics. In this paper we study the logical properties of DL^N and their relationships with the KLM postulates. We use various versions of the KLM postulates to deepen the comparison with related work, and illustrate the different tradeoffs between opposite expressivity requirements adopted by each approach.

AAMAS Conference 2016 Conference Paper

Generalized Agent-mediated Procurement Auctions

• Piero A. Bonatti
• Marco Faella
• Clemente Galdi
• Luigi Sauro

Procurement auctions (where the auctioneer needs a service and bidders offer it at their own conditions) are an appealing method for on-line service selection. They can improve service features and cost by exploiting the competition between different service providers. Software agents, acting on behalf of human users and organizations, are essential in making such auctions practical and usable. Since conveying user preferences to the agents in a faithful and complete way is virtually impossible, we advocate an approximate approach, where only partial preferences are formalized, and users pick their choice from a short list of options selected by the agents by means of those partial preferences. Another peculiarity of our scenarios is that there may be no contracts with null utility for a given bidder. These features affect the classical, desirable properties of standard auction mechanisms. We prove some impossibility results concerning truthfulness and (a qualitative analogue of) revenue. Then, we investigate a novel auction mechanism that is almost truthful in the sense that any strategic deviation from truthfulness has limited impact on the auctioneer’s revenue.

MFCS Conference 2013 Conference Paper

Auctions for Partial Heterogeneous Preferences

• Piero A. Bonatti
• Marco Faella
• Clemente Galdi
• Luigi Sauro

Abstract Online privacy provides fresh motivations to generalized auctions where: (i) preferences over bids may be partial, because of lack of knowledge and formalization difficulties; (ii) the preferences of auctioneers and bidders may be heterogeneous and unrelated. We tackle these generalized scenarios by introducing a few natural generalizations of second-price auctions, and by investigating which of their classical properties are preserved under which conditions.

IJCAI Conference 2009 Conference Paper

• Piero A. Bonatti
• Marco Faella
• Luigi Sauro

We analyze the complexity of reasoning with circumscribed low-complexity DLs such as DL-lite and the EL family, under suitable restrictions on the use of abnormality predicates. We prove that in circumscribed DL-liteR complexity drops from NExpNP to the second level of the polynomial hierarchy. In EL, reasoning remains ExpTime-hard, in general. However, by restricting the possible occurrences of existential restrictions, we obtain membership in Σp 2 and Πp 2 for an extension of EL.

AIJ Journal 2008 Journal Article

Erratum to: Reasoning with infinite stable models [Artificial Intelligence 156 (1) (2004) 75–111]

• Piero A. Bonatti

Theorem 16 in [Piero A. Bonatti, Reasoning with infinite stable models, Artificial Intelligence 156 (1) (2004) 75–111] states that ground skeptical and credulous inferences under the stable model semantics are decidable when the given normal logic program is finitary. Giovanni Criscuolo and Nicola Leone independently observed in personal communications that the proof of this theorem relies on an unproved assumption that—at the best of our current knowledge—might turn out to be false. In this note we correct Theorem 16 by adding the set of odd-cyclic atoms to the inputs of the computation, and argue that this change has no impact on the current applications of the theory of finitary programs.

ECAI Conference 2006 Conference Paper

Advanced Policy Explanations on the Web

• Piero A. Bonatti
• Daniel Olmedilla
• Joachim Peer

The frameworks for protecting security and privacy can be effective only if common users—with no training in computer science or logic—increase their awareness and control over the policy applied by the systems they interact with. Towards this end, we introduce a mechanism for answering why, why-not, how-to, and what-if queries on rule-based policies for trust negotiation. Our framework is lightweight and scalable but it fulfills the main goals of modern explanation facilities. We adopt a novel tabled explanation structure, that simultaneously shows local and global (intra-proof and inter-proof) information, thereby facilitating navigation. Answers are focussed by removing irrelevant parts with suitable heuristics.

ECAI Conference 2004 Conference Paper

Abduction over Unbounded Domains via ASP

• Piero A. Bonatti

AIJ Journal 2004 Journal Article

Reasoning with infinite stable models

• Piero A. Bonatti

This paper illustrates extensively the theoretical properties, the implementation issues, and the programming style underlying finitary programs. They are a class of normal logic programs whose consequences under the stable model semantics can be effectively computed, despite the fact that finitary programs admit function symbols (hence infinite domains) and recursion. From a theoretical point of view, finitary programs are interesting because they enjoy properties that are extremely unusual for a nonmonotonic formalism, such as compactness. From the application point of view, the theory of finitary programs shows how the existing technology for answer set programming can be extended from problem solving below the second level of the polynomial hierarchy to all semidecidable problems. Moreover, finitary programs allow a more natural encoding of recursive data structures and may increase the performance of credulous reasoners.

IJCAI Conference 2003 Conference Paper

On the Undecidability of Description and Dynamic Logics with Recursion and Counting

• Piero A. Bonatti

The evolution of Description Logics (DLs) and Propositional Dynamic Logics produced a hierar­ chy of decidable logics with multiple maximal el­ ements. It would be desirable to combine different maximal logics into one super-logic, but then in­ ference may turn out to be undecidable. Then it is important to characterize the decidability thresh­ old for these logics. In this perspective, an interest­ ing open question pointed out by Sattler and Vardi [Sattler and Vardi, 1999] is whether inference in a hybrid μ-calculus with restricted forms of graded modalities is decidable, and which complexity class it belongs to. In this paper we prove that this calcu­ lus and the corresponding are un­ decidable. Second, we prove undecidability results for logics that support both a transitive closure op­ erator over roles and number restrictions.

NMR Workshop 2002 Conference Paper

Abduction, ASP and open logic programs

• Piero A. Bonatti

Open logic programs and open entailment have been recently proposed as an abstract framework for the verification of incomplete specifications based upon normal logic programs and the stable model semantics. There are obvious analogies between open predicates and abducible predicates. Their extension is not specified in the program. However, despite superficial similarities, there are features of open programs that have no immediate counterpart in the framework of abduction and viceversa. Similarly, open programs cannot be immediately simulated with answer set programming (ASP). In this paper we start a thorough investigation of the relationships between open inference, abduction and ASP. We shall prove that open programs generalize the other two frameworks. Similarities and differences between the three frameworks will be analyzed formally. The generalized framework suggests interesting extensions of abduction under the generalized stable model semantics. In some cases, we will be able to reduce open inference to abduction and ASP, thereby characterizing the computational complexity of credulous and skeptical open inference for finite, function-free open programs. At the same time, the aforementioned reduction opens the way to new applications of abduction and ASP.

JELIA Conference 2002 Conference Paper

Towards Service Description Logics

• Piero A. Bonatti

Abstract Semantic service description and matchmaking are needed in embedded and disappearing computing, cooperative multiagent systems, and the semantic web. Standard program semantics formalizations are not suited to modeling service semantics, because they are generic w. r. t. the data manipulated by programs, and because computation details are often irrelevant to the aforementioned applications of service descriptions. An ontology-based approach seems more appropriate. However, current ontology specification languages do not have primitives for service description. In this paper, we identify some useful service description constructs and study their impact on the decidability of reasoning with description logics.

CSL Conference 1998 Conference Paper

A Sequent Calculus for Circumscription

• Piero A. Bonatti
• Nicola Olivetti

Abstract In this paper, we introduce a sequent calculus CIRC for propositional Circumscription. This work is part of a larger project, aiming at a uniform proof-theoretic reconstruction of the major families of non-monotonic logics. Among the novelties of the calculus, we mention that CIRC is analytic and comprises an axiomatic rejection method, which allows for a fully detailed formalization of the nonmonotonic aspects of inference.

TCS Journal 1996 Journal Article

Querying disjunctive databases through nonmonotonic logics

• Piero A. Bonatti
• Thomas Eiter

Query languages for retrieving information from disjunctive databases are an interesting open area of research. In this paper we study the expressive power of major nonmonotonic formalisms — such as circumscription, default logic, autoepistemic logic and some logic programming languages — used as query languages over disjunctive databases. For this aim, we define the semantics of query expressions formulated in different nonmonotonic logics. The expressive power of the languages that we consider has been explored in the context of relational databases. Here, we extend this study to disjunctive databases; as a result, we obtain a finer-grained characterization of the expressiveness of those languages and interesting fragments thereof. For instance, we show that there exist simple queries that cannot be expressed by any preferential semantics (including the minimal model semantics and the various forms of circumscription), while they can be expressed in default and autoepistemic logic. Secondly, we show that default logic, autoepistemic logic and some of their fragments express the same class of Boolean queries, which turns out to be a strict subclass of the ∑ p 2-recognizable Boolean queries. The latter result is proved by means of a new technique, based on a counting argument. Then we prove that under the assumption that the database consists of clauses whose length is bounded by some constant, default logic and autoepistemic logic express all of the ∑ p 2-recognizable Boolean queries, while preference-based logics cannot. These results hold for brave reasoning; we obtain dual results for cautious reasoning. Our results appear to be interesting both in the area of database theory and in the area of knowledge representation.