Showing 1–12 of 12 results for author: Bonatti, P A

Defeasible reasoning in Description Logics: an overview on DL^N

Authors: Piero A. Bonatti, Iliana M. Petrova, Luigi Sauro

Abstract: DL^N is a recent approach that extends description logics with defeasible reasoning capabilities. In this paper we provide an overview on DL^N, illustrating the underlying knowledge engineering requirements as well as the characteristic features that preserve DL^N from some recurrent semantic and computational drawbacks. We also compare DL^N with some alternative nonmonotonic semantics, enlighteni… ▽ More DL^N is a recent approach that extends description logics with defeasible reasoning capabilities. In this paper we provide an overview on DL^N, illustrating the underlying knowledge engineering requirements as well as the characteristic features that preserve DL^N from some recurrent semantic and computational drawbacks. We also compare DL^N with some alternative nonmonotonic semantics, enlightening the relationships between the KLM postulates and DL^N. △ Less

Submitted 17 September, 2020; v1 submitted 10 September, 2020; originally announced September 2020.

Machine Understandable Policies and GDPR Compliance Checking

Authors: Piero A. Bonatti, Sabrina Kirrane, Iliana M. Petrova, Luigi Sauro

Abstract: The European General Data Protection Regulation (GDPR) calls for technical and organizational measures to support its implementation. Towards this end, the SPECIAL H2020 project aims to provide a set of tools that can be used by data controllers and processors to automatically check if personal data processing and sharing complies with the obligations set forth in the GDPR. The primary contributio… ▽ More The European General Data Protection Regulation (GDPR) calls for technical and organizational measures to support its implementation. Towards this end, the SPECIAL H2020 project aims to provide a set of tools that can be used by data controllers and processors to automatically check if personal data processing and sharing complies with the obligations set forth in the GDPR. The primary contributions of the project include: (i) a policy language that can be used to express consent, business policies, and regulatory obligations; and (ii) two different approaches to automated compliance checking that can be used to demonstrate that data processing performed by data controllers / processors complies with consent provided by data subjects, and business processes comply with regulatory obligations set forth in the GDPR. △ Less

Submitted 24 January, 2020; originally announced January 2020.

Fast Compliance Checking with General Vocabularies

Authors: P. A. Bonatti, L. Ioffredo, I. M. Petrova, L. Sauro

Abstract: We address the problem of complying with the GDPR while processing and transferring personal data on the web. For this purpose we introduce an extensible profile of OWL2 for representing data protection policies. With this language, a company's data usage policy can be checked for compliance with data subjects' consent and with a formalized fragment of the GDPR by means of subsumption queries. The… ▽ More We address the problem of complying with the GDPR while processing and transferring personal data on the web. For this purpose we introduce an extensible profile of OWL2 for representing data protection policies. With this language, a company's data usage policy can be checked for compliance with data subjects' consent and with a formalized fragment of the GDPR by means of subsumption queries. The outer structure of the policies is restricted in order to make compliance checking highly scalable, as required when processing high-frequency data streams or large data volumes. However, the vocabularies for specifying policy properties can be chosen rather freely from expressive Horn fragments of OWL2. We exploit IBQ reasoning to integrate specialized reasoners for the policy language and the vocabulary's language. Our experiments show that this approach significantly improves performance. △ Less

Submitted 16 January, 2020; originally announced January 2020.

Comments: arXiv admin note: substantial text overlap with arXiv:2001.05390

Real Time Reasoning in OWL2 for GDPR Compliance

Authors: P. A. Bonatti, L. Ioffredo, I. Petrova, L. Sauro, I. R. Siahaan

Abstract: 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 lan… ▽ More 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 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. PL and its integration with OWL2's profiles constitute new tractable fragments of OWL2. We prove also some negative results, concerning the intractability of unrestricted reasoning in PL, and the limitations posed on ontology import. △ Less

Submitted 15 January, 2020; originally announced January 2020.

Optimizing the computation of overriding

Authors: Piero Andrea Bonatti, Iliana Mineva Petrova, Luigi Sauro

Abstract: We introduce optimization techniques for reasoning in DLN---a recently introduced family of nonmonotonic description logics whose characterizing features appear well-suited to model the applicative examples naturally arising in biomedical domains and semantic web access control policies. Such optimizations are validated experimentally on large KBs with more than 30K axioms. Speedups exceed 1 order… ▽ More We introduce optimization techniques for reasoning in DLN---a recently introduced family of nonmonotonic description logics whose characterizing features appear well-suited to model the applicative examples naturally arising in biomedical domains and semantic web access control policies. Such optimizations are validated experimentally on large KBs with more than 30K axioms. Speedups exceed 1 order of magnitude. For the first time, response times compatible with real-time reasoning are obtained with nonmonotonic KBs of this size. △ Less

Submitted 16 July, 2015; originally announced July 2015.

Partial Preferences for Mediated Bargaining

Authors: Piero A. Bonatti, Marco Faella, Luigi Sauro

Abstract: In this work we generalize standard Decision Theory by assuming that two outcomes can also be incomparable. Two motivating scenarios show how incomparability may be helpful to represent those situations where, due to lack of information, the decision maker would like to maintain different options alive and defer the final decision. In particular, a new axiomatization is given which turns out to be… ▽ More In this work we generalize standard Decision Theory by assuming that two outcomes can also be incomparable. Two motivating scenarios show how incomparability may be helpful to represent those situations where, due to lack of information, the decision maker would like to maintain different options alive and defer the final decision. In particular, a new axiomatization is given which turns out to be a weakening of the classical set of axioms used in Decision Theory. Preliminary results show how preferences involving complex distributions are related to judgments on single alternatives. △ Less

Submitted 3 April, 2014; originally announced April 2014.

Comments: In Proceedings SR 2014, arXiv:1404.0414

Journal ref: EPTCS 146, 2014, pp. 105-111

Defeasible Inclusions in Low-Complexity DLs

Authors: Piero A. Bonatti, Marco Faella, Luigi Sauro

Abstract: Some of the applications of OWL and RDF (e.g. biomedical knowledge representation and semantic policy formulation) call for extensions of these languages with nonmonotonic constructs such as inheritance with overriding. Nonmonotonic description logics have been studied for many years, however no practical such knowledge representation languages exist, due to a combination of semantic difficulties… ▽ More Some of the applications of OWL and RDF (e.g. biomedical knowledge representation and semantic policy formulation) call for extensions of these languages with nonmonotonic constructs such as inheritance with overriding. Nonmonotonic description logics have been studied for many years, however no practical such knowledge representation languages exist, due to a combination of semantic difficulties and high computational complexity. Independently, low-complexity description logics such as DL-lite and EL have been introduced and incorporated in the OWL standard. Therefore, it is interesting to see whether the syntactic restrictions characterizing DL-lite and EL bring computational benefits to their nonmonotonic versions, too. In this paper we extensively investigate the computational complexity of Circumscription when knowledge bases are formulated in DL-lite_R, EL, and fragments thereof. We identify fragments whose complexity ranges from P to the second level of the polynomial hierarchy, as well as fragments whose complexity raises to PSPACE and beyond. △ Less

Submitted 16 January, 2014; originally announced January 2014.

Journal ref: Journal Of Artificial Intelligence Research, Volume 42, pages 719-764, 2011

The Complexity of Circumscription in DLs

Authors: Piero A. Bonatti, Carsten Lutz, Frank Wolter

Abstract: As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an inter… ▽ More As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an interesting alternative approach to nonmonotonic DLs that, in particular, supports defeasible inheritance in a natural way. We study DLs extended with circumscription under different language restrictions and under different constraints on the sets of minimized, fixed, and varying predicates, and pinpoint the exact computational complexity of reasoning for DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed predicates include only concept names but no role names, then reasoning is complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number of minimized and fixed predicates is bounded by a constant. If roles can be minimized or fixed, then complexity ranges from NExpTime^NP to undecidability. △ Less

Submitted 15 January, 2014; originally announced January 2014.

Journal ref: Journal Of Artificial Intelligence Research, Volume 35, pages 717-773, 2009

A decidable subclass of finitary programs

Authors: Sabrina Baselice, Piero A. Bonatti

Abstract: Answer set programming - the most popular problem solving paradigm based on logic programs - has been recently extended to support uninterpreted function symbols. All of these approaches have some limitation. In this paper we propose a class of programs called FP2 that enjoys a different trade-off between expressiveness and complexity. FP2 programs enjoy the following unique combination of propert… ▽ More Answer set programming - the most popular problem solving paradigm based on logic programs - has been recently extended to support uninterpreted function symbols. All of these approaches have some limitation. In this paper we propose a class of programs called FP2 that enjoys a different trade-off between expressiveness and complexity. FP2 programs enjoy the following unique combination of properties: (i) the ability of expressing predicates with infinite extensions; (ii) full support for predicates with arbitrary arity; (iii) decidability of FP2 membership checking; (iv) decidability of skeptical and credulous stable model reasoning for call-safe queries. Odd cycles are supported by composing FP2 programs with argument restricted programs. △ Less

Submitted 21 July, 2010; originally announced July 2010.

Journal ref: Theory and Practice of Logic Programming (2010), 10:481-496 Cambridge University Press

On finitely recursive programs

Authors: Sabrina Baselice, Piero A. Bonatti, Giovanni Criscuolo

Abstract: Disjunctive finitary programs are a class of logic programs admitting function symbols and hence infinite domains. They have very good computational properties, for example ground queries are decidable while in the general case the stable model semantics is highly undecidable. In this paper we prove that a larger class of programs, called finitely recursive programs, preserves most of the good p… ▽ More Disjunctive finitary programs are a class of logic programs admitting function symbols and hence infinite domains. They have very good computational properties, for example ground queries are decidable while in the general case the stable model semantics is highly undecidable. In this paper we prove that a larger class of programs, called finitely recursive programs, preserves most of the good properties of finitary programs under the stable model semantics, namely: (i) finitely recursive programs enjoy a compactness property; (ii) inconsistency checking and skeptical reasoning are semidecidable; (iii) skeptical resolution is complete for normal finitely recursive programs. Moreover, we show how to check inconsistency and answer skeptical queries using finite subsets of the ground program instantiation. We achieve this by extending the splitting sequence theorem by Lifschitz and Turner: We prove that if the input program P is finitely recursive, then the partial stable models determined by any smooth splitting omega-sequence converge to a stable model of P. △ Less

Submitted 19 January, 2009; originally announced January 2009.

Comments: 26 pages, Preliminary version in Proc. of ICLP 2007, Best paper award

Journal ref: Theory and Practice of Logic Programming, 9(2), 213-238, 2009

The Complexity of Enriched Mu-Calculi

Authors: Piero A. Bonatti, Carsten Lutz, Aniello Murano, Moshe Y. Vardi

Abstract: The fully enriched μ-calculus is the extension of the propositional μ-calculus with inverse programs, graded modalities, and nominals. While satisfiability in several expressive fragments of the fully enriched μ-calculus is known to be decidable and ExpTime-complete, it has recently been proved that the full calculus is undecidable. In this paper, we study the fragments of the fully enr… ▽ More The fully enriched μ-calculus is the extension of the propositional μ-calculus with inverse programs, graded modalities, and nominals. While satisfiability in several expressive fragments of the fully enriched μ-calculus is known to be decidable and ExpTime-complete, it has recently been proved that the full calculus is undecidable. In this paper, we study the fragments of the fully enriched μ-calculus that are obtained by dropping at least one of the additional constructs. We show that, in all fragments obtained in this way, satisfiability is decidable and ExpTime-complete. Thus, we identify a family of decidable logics that are maximal (and incomparable) in expressive power. Our results are obtained by introducing two new automata models, showing that their emptiness problems are ExpTime-complete, and then reducing satisfiability in the relevant logics to these problems. The automata models we introduce are two-way graded alternating parity automata over infinite trees (2GAPTs) and fully enriched automata (FEAs) over infinite forests. The former are a common generalization of two incomparable automata models from the literature. The latter extend alternating automata in a similar way as the fully enriched μ-calculus extends the standard μ-calculus. △ Less

Submitted 22 September, 2008; v1 submitted 2 September, 2008; originally announced September 2008.

Comments: A preliminary version of this paper appears in the Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), 2006. This paper has been selected for a special issue in LMCS

ACM Class: F.3.1; F.4.1

Journal ref: Logical Methods in Computer Science, Volume 4, Issue 3 (September 22, 2008) lmcs:993

Abduction, ASP and Open Logic Programs

Authors: Piero A. Bonatti

Abstract: 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. However, despite superficial similarities, there are features of open programs that have no immediate counterpar… ▽ More 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. 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. 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 estimating its computational complexity. At the same time, the aforementioned reduction opens the way to new applications of abduction and ASP. △ Less

Submitted 7 July, 2002; originally announced July 2002.

Comments: 7 pages, NMR'02 Workshop

ACM Class: I.2.3; I.2.4