Search

Recently, explanations for query answers under existential rules have been investigated, where an explanation is an inclusion-minimal subset of a given database that, together with the ontology, entails the query. In this paper, we take a step further and study explanations under different minimality criteria. In particular, we first study cardinality-minimal explanations and hence focus on deriving explanations of minimum size. We then study a more general preference order induced by a weight distribution. We assume that every database fact is annotated with a (penalization) weight, and we are interested in explanations with minimum overall weight. For both preference orders, we study a variety of explanation problems, such as recognizing a preferred explanation, all preferred explanations, a relevant or necessary fact, and the existence of a preferred explanation not containing forbidden sets of facts. We provide a detailed complexity analysis for all the aforementioned problems, thereby providing a more complete picture for explaining query answers under existential rules.

Ontology-mediated query answering is a paradigm that seeks to exploit the semantic knowledge expressed in terms of ontologies to improve query answers over incomplete data sources. In this paper, we focus on description logic ontologies, and study the problem of explaining why an ontology-mediated query is entailed from a given data source. Specifically, we view explanations as minimal sets of assertions from an ABox, which satisfy the ontologymediated query. Based on such explanations, we study a variety of problems taken from the recent literature on explanations (studied for existential rules), such as recognizing all minimal explanations. Our results establish tight connections between intractable explanation problems and variants of propositional satisfiability problems. We provide insights on the inherent computational difficulty of deriving explanations for ontology-mediated queries.

Aggregating preferences over combinatorial domains has many applications in artificial intelligence (AI). Given the inherent exponential nature of preferences over combinatorial domains, compact representation languages are needed to represent them, and ( m )CP-nets are among the most studied ones. Sequential and global voting are two different ways of aggregating preferences represented via CP-nets. In sequential voting, agents' preferences are aggregated feature-by-feature. For this reason, sequential voting may exhibit voting paradoxes, i.e., the possibility to select sub-optimal outcomes when preferences have specific feature dependencies. To avoid paradoxes in sequential voting, one has often assumed the (quite) restrictive constraint of O -legality, which imposes a shared common topological order among all the agents' CP-nets. On the contrary, in global voting, CP-nets are considered as a whole during the preference aggregation process. For this reason, global voting is immune from the voting paradoxes of sequential voting, and hence there is no need to impose restrictions over the CP-nets' structure when preferences are aggregated via global voting. Sequential voting over O -legal CP-nets received much attention, and O -legality of CP-nets has often been required in other studies. On the other hand, global voting over non- O -legal CP-nets has not carefully been analyzed, despite it was explicitly stated in the literature that a theoretical comparison between global and sequential voting was highly promising and a precise complexity analysis for global voting has been asked for multiple times. In quite a few works, only very partial results on the complexity of global voting over CP-nets have been given. In this paper, we start to fill this gap by carrying out a thorough computational complexity analysis of global voting tasks, for Pareto and majority voting, over not necessarily O -legal acyclic binary polynomially connected ( m )CP-nets. We show that all these problems belong to various levels of the polynomial hierarchy, and some of them are even in P or LOGSPACE. Our results are a notable achievement, given that the previously known upper bound for most of these problems was the complexity class EXPTIME. We provide various exact complexity results showing tight lower bounds and matching upper bounds for problems that (up to now) did not have any explicit non-obvious lower bound.

The complexity class Θ^P_2, which is the class of languages recognizable by deterministic Turing machines in polynomial time with at most logarithmic many calls to an NP oracle, received extensive attention in the literature. Its complete problems can be characterized by different specific tasks, such as deciding whether the optimum solution of an NP problem is unique, or whether it is in some sense “odd” (e.g., whether its size is an odd number). In this paper, we introduce a new characterization of this class and its generalization Θ^P_k to the k-th level of the polynomial hierarchy. We show that problems in Θ^P_k are also those whose solution involves deciding, for two given sets A and B of instances of two Σ^P_{k−1}-complete (or Π^P_{k−1}-complete) problems, whether the number of “yes”-instances in A is greater than those in B. Moreover, based on this new characterization, we provide a novel sufficient condition for Θ^P_k-hardness. We also define the general problem Comp-Valid_k, which is proven here Θ^P_{k+1}-complete. Comp-Valid_k is the problem of deciding, given two sets A and B of quantified Boolean formulas with at most k alternating quantifiers, whether the number of valid formulas in A is greater than those in B. Notably, the problem Comp-Sat of deciding whether a set contains more satisfiable Boolean formulas than another set, which is a particular case of Comp-Valid_1, demonstrates itself as a very intuitive Θ^P_2-complete problem. Nonetheless, to our knowledge, it eluded its formal definition to date. In fact, given its strict adherence to the count-and-compare semantics here introduced, Comp-Valid_k is among the most suitable tools to prove Θ^P_k-hardness of problems involving the counting and comparison of the number of “yes”-instances in two sets. We support this by showing that the Θ^P_2-hardness of the Max voting scheme over mCP-nets is easily obtained via the new characterization of Θ^P_k introduced in this paper.

mCP-nets are an expressive and intuitive formalism based on CP-nets to reason about preferences of groups of agents. The dominance semantics of mCP-nets is based on the concept of voting, and different voting schemes give rise to different dominance semantics for the group. Unlike CP-nets, which received an extensive complexity analysis, mCP-nets, as reported multiple times in the literature, lack a precise study of the voting tasks’ complexity. Prior to this work, only a complexity analysis of brute-force algorithms for these tasks was available, and this analysis only gave EXPTIME upper bounds for most of those problems. In this paper, we start to fill this gap by carrying out a precise computational complexity analysis of voting tasks on acyclic binary polynomially connected mCP-nets whose constituents are standard CP-nets. Interestingly, all these problems actually belong to various levels of the polynomial hierarchy, and some of them even belong to PTIME or LOGSPACE. Furthermore, for most of these problems, we provide completeness results, which show tight lower bounds for problems that (up to date) did not have any explicit non-obvious lower bound.

Millions of RDF links connect data providers on the Web of Linked Data. Here, navigability is a key issue. This poster provides a preliminary quantitative analysis of this fundamental feature.

Querying inconsistent knowledge bases is a problem that has attracted a great deal of interest over the last decades. While several semantics of query answering have been proposed, and their complexity is rather well-understood, little attention has been paid to the problem of explaining query answers. Explainability has recently become a prominent problem in different areas of AI. In particular, explaining query answers allows users to understand not only what is entailed by an inconsistent knowledge base, but also why. In this paper, we address the problem of explaining query answers for existential rules under three popular inconsistency-tolerant semantics, namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs semantics. We provide a thorough complexity analysis for a wide range of existential rule languages and for different complexity measures.

Querying inconsistent ontological knowledge bases is an important problem in practice, for which several inconsistencytolerant query answering semantics have been proposed, including query answering relative to all repairs, relative to the intersection of repairs, and relative to the intersection of closed repairs. In these semantics, one assumes that the input database is erroneous, and the notion of repair describes a maximally consistent subset of the input database, where different notions of maximality (such as subset and cardinality maximality) are considered. In this paper, we give a precise picture of the computational complexity of inconsistencytolerant (Boolean conjunctive) query answering in a wide range of Datalog± languages under the cardinality-based versions of the above three repair semantics.

Ontology-mediated query answering is an extensively studied paradigm, which aims at improving query answers with the use of a logical theory. In this paper, we focus on ontology languages based on existential rules, and we carry out a thorough complexity analysis of the problem of explaining query answers in terms of minimal subsets of database facts and related tasks

The chase is a well-established family of algorithms used to materialize Knowledge Bases (KBs) for tasks like query answering under dependencies or data cleaning. A general problem of chase algorithms is that they might perform redundant computations. To counter this problem, we introduce the notion of Trigger Graphs (TGs), which guide the execution of the rules avoiding redundant computations. We present the results of an extensive theoretical and empirical study that seeks to answer when and how TGs can be computed and what are the benefits of TGs when applied over real-world KBs. Our results include introducing algorithms that compute (minimal) TGs. We implemented our approach in a new engine, called GLog, and our experiments show that it can be significantly more efficient than the chase enabling us to materialize Knowledge Graphs with 17B facts in less than 40 min using a single machine with commodity hardware.

Ontology-mediated query answering is an extensively studied paradigm, which aims at improving query answers with the use of a logical theory. As a form of logical entailment, ontology-mediated query answering is fully interpretable, which makes it possible to derive explanations for query answers. Surprisingly, however, explaining answers for ontology-mediated queries has received little attention for ontology languages based on existential rules. In this paper, we close this gap, and study the problem of explaining query answers in terms of minimal subsets of database facts. We provide a thorough complexity analysis for several decision problems associated with minimal explanations under existential rules.

Il contributo analizza la disciplina, contenuta nel Trattato sul funzionamento dell'Unione Europea e nelle principali fonti di diritto derivato, in tema di libera prestazione di servizi e libertà di stabilimento delle imprese e dei lavoratori autonomi, alla luce delle fondamentali evoluzioni che nei decenni sono state introdotte dalla giurisprudenza della Corte di Lussemburgo su numerosi versanti regolativi: innovazioni spesso, ma non sempre, apprezzabili favorevolmente in termini di politica del diritto, secondo l'opinione dell'autore.

Il contributo analizza la disciplina dell'UE in tema di riconoscimento delle qualifiche e dei titoli professionali di lavoratori subordinati, autonomi, professionisti, imprenditori (comprese le questioni inerenti a titoli e cittadini extra-UE). In particolare, vengono considerate le regole semplificate al fine della prestazione di servizi transfrontaliera e soprattutto il triplice regime di riconoscimento (automatico per armonizzazione della disciplina materiale speciale, per esperienza professionale, regime generale residuale) finalizzato alla libertà di stabilimento, oltreché la casistica specifica (riconoscimento parziale, accesso al pubblico impiego, valenza dei tirocini professionali, disciplina speciale per le professioni legali, etc.). Il delineato quadro denota un’evoluzione normativa notevole negli ultimi due decenni, assai apprezzabile ma ancora non pienamente soddisfacente.

Several semantics have been proposed to query inconsistent ontological knowledge bases, including the intersection of repairs and the intersection of closed repairs as two approximate inconsistency-tolerant semantics. In this paper, we analyze the complexity of conjunctive query answering under these two semantics for a wide range of Datalog+/- languages. We consider both the standard setting, where errors may only be in the database, and the generalized setting, where also the rules of a Datalog+/- knowledge base may be erroneous.

The nucleolus is a well-known solution concept for coalitional games to fairly distribute the total available worth among the players. The nucleolus is known to be NP -hard to compute over compact coalitional games, that is, over games whose functions specifying the worth associated with each coalition are encoded in terms of polynomially computable functions over combinatorial structures. In particular, hardness results have been exhibited over minimum spanning tree games, threshold games, and flow games. However, due to its intricate definition involving reasoning over exponentially many coalitions, a nontrivial upper bound on its complexity was missing in the literature and looked for. This article faces this question and precisely characterizes the complexity of the nucleolus, by exhibiting an upper bound that holds on any class of compact games, and by showing that this bound is tight even on the (structurally simple) class of graph games. The upper bound is established by proposing a variant of the standard linear-programming based algorithm for nucleolus computation and by studying a framework for reasoning about succinctly specified linear programs, which are contributions of interest in their own. The hardness result is based on an elaborate combinatorial reduction, which is conceptually relevant for it provides a “measure” of the computational cost to be paid for guaranteeing voluntary participation to the distribution process. In fact, the pre-nucleolus is known to be efficiently computable over graph games, with this solution concept being defined as the nucleolus but without guaranteeing that each player is granted with it at least the worth she can get alone, that is, without collaborating with the other players. Finally, this article identifies relevant tractable classes of coalitional games, based on the notion of type of a player. Indeed, in most applications where many players are involved, it is often the case that such players do belong in fact to a limited number of classes, which is known in advance and may be exploited for computing the nucleolus in a fast way.

The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs $\mathcal{G}$ and $\mathcal{H}$, decide whether $\mathcal{H}$ consists precisely of all minimal transversals of $\mathcal{G}$ (in which case we say that $\mathcal{G}$ is the dual of $\mathcal{H}$). This problem is equivalent to deciding whether two given non-redundant monotone DNFs are dual. It is known that non-DUAL, the complementary problem to DUAL, is in $\mathrm{GC}(\log^2 n,\mathrm{PTIME})$, where $\mathrm{GC}(f(n),\mathcal{C})$ denotes the complexity class of all problems that after a nondeterministic guess of $O(f(n))$ bits can be decided (checked) within complexity class $\mathcal{C}$. It was conjectured that non-DUAL is in $\mathrm{GC}(\log^2 n,\mathrm{LOGSPACE})$. In this paper we prove this conjecture and actually place the non-DUAL problem into the complexity class $\mathrm{GC}(\log^2 n,\mathrm{TC}^0)$ which is a subclass of $\mathrm{GC}(\log^2 n,\mathrm{LOGSPACE})$. We here refer to the logtime-uniform version of $\mathrm{TC}^0$, which corresponds to $\mathrm{FO(COUNT)}$, i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for non-DUAL that requires to guess $O(\log^2 n)$ bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in $\mathrm{FO(COUNT)}$. From this result, by the well known inclusion $\mathrm{TC}^0\subseteq\mathrm{LOGSPACE}$, it follows that DUAL belongs also to $\mathrm{DSPACE}[\log^2 n]$. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs $\mathcal{G}$ and $\mathcal{H}$, computes in quadratic logspace a transversal of $\mathcal{G}$ missing in $\mathcal{H}$., Restructured the presentation in order to be the extended version of a paper that will shortly appear in SIAM Journal on Computing

Coalitional games serve the purpose of modeling payoff distribution problems in scenarios where agents can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. In the classical Transferable Utility (TU) setting, coalition worths can be freely distributed amongst agents. However, in several application scenarios, this is not the case and the Non-Transferable Utility setting (NTU) must be considered, where additional application-oriented constraints are imposed on the possible worth distributions. In this paper, an approach to define NTU games is proposed which is based on describing allowed distributions via a set of mixed-integer linear constraints applied to an underlying TU game. It is shown that such games allow non-transferable conditions on worth distributions to be specified in a natural and succinct way. The properties and the relationships among the most prominent solution concepts for NTU games that hold when they are applied on (mixed-integer) constrained games are investigated. Finally, a thorough analysis is carried out to assess the impact of issuing constraints on the computational complexity of some of these solution concepts.

Il saggio affronta le più delicate questioni interpretative in tema di contratto di lavoro a tempo determinato nel settore pubblico, mettendo in risalto le incertezze giurisprudenziali registrate nell'ultimo quinquennio e le difficoltà applicative nel colmare le attuali aporie legislative.