In recent years, explainable AI has become a major focus of research, driven by the need to better understand how AI systems arrive at their decisions in order to ensure trust and effective deployment. A central challenge in this field is the explanation of classifiers. Existing approaches typically distinguish between local explanations, which account for a classifier’s decision on an individual input, and global explanations, which aim to characterize the classifier’s behavior as a whole, independent of any particular input. This work concentrates on global explanations and characterizes classification decisions through "maximal" sufficient conditions that, when satisfied, guarantee that the classifier assigns the desired class to any input. We present a detailed analysis of the computational complexity of key problems in this setting across several important families of classifiers considered in the literature.

Dung's abstract Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning more intuitive and expressive. In this paper, we present the Knowledge-based Argumentation Framework (KAF), an extension of AF with a Knowledge Base (KB) expressed in DL-Lite, which includes concept and role instances describing the topology of an AF, besides additional knowledge on the domain. The KAF semantics is given by a set of KAF extensions, each consisting of an extension of the underlying AF together with a ``pertinent'' subset of the original KB, which is obtained by discarding assertions referring to arguments that have been ruled out in the AF extension. Then, the framework is further expanded into the Constrained KAF (CKAF), where a set of restricted relational calculus formulae is used for reasoning over `feasible' subframeworks that satisfy the formulae and minimally differ from the original framework. We thoroughly investigate the computational complexity of classical reasoning problems under popular argumentation semantics, and show that well-known AF-based frameworks are special cases of CKAF.

Explainable AI has garnered considerable attention in recent years, as understanding the reasons behind decisions made by AI systems is crucial for their successful adoption. Explaining classifiers' behavior is one prominent problem. Work in this area has proposed notions of both local and global explanations, where the former are concerned with explaining a classifier's behavior for a specific instance, while the latter are concerned with explaining the overall classifier's behavior regardless of any specific instance. In this paper, we focus on global explanations, and explain classification in terms of ``minimal'' necessary conditions for the classifier to assign a specific class to a generic instance. We carry out a thorough complexity analysis of the problem for natural minimality criteria and important families of classifiers considered in the literature.

There are many applications where an autonomous agent can perform many sets of actions. It must choose one set of actions based on some behavioral constraints on the agent. Past work has used deontic logic to declaratively express such constraints in logic, and developed the concept of a feasible status set (FSS), a set of actions that satisfy these constraints. However, multiple FSSs may exist and an agent needs to choose one in order to act. As there may be many different objective functions to evaluate status sets, we propose the novel concept of Pareto-optimal FSSs or POSS. We show that checking if a status set is a POSS is co-NP-hard. We develop an algorithm to find a POSS and in special cases when the objective functions are monotonic (or anti-monotonic), we further develop more efficient algorithms. Finally, we conduct experiments to show the efficacy of our approach and we discuss possible ways to handle multiple Pareto-optimal Status Sets.

Abstract Data exchange, the problem of transferring data from a source schema to a target schema, has been studied for several years. The semantics of answering positive queries over the target schema has been defined in early work, but little attention has been paid to more general queries. A few proposals of semantics for more general queries exist but they either do not properly extend the standard semantics under positive queries, giving rise to counterintuitive answers, or they make query answering undecidable even for the most important data exchange settings, for example, with weakly-acyclic dependencies. The goal of this paper is to provide a new semantics for data exchange that is able to deal with general queries. At the same time, we want our semantics to coincide with the classical one when focusing on positive queries, and to not trade-off too much in terms of complexity of query answering. We show that query answering is undecidable in general under the new semantics, but it is $\text{co}\text{NP}\text{-complete}$ when the dependencies are weakly-acyclic. Moreover, in the latter case, we show that exact answers under our semantics can be computed by means of logic programs with choice, thus exploiting existing efficient systems. For more efficient computations, we also show that our semantics allows for the construction of a representative target instance, similar in spirit to a universal solution, that can be exploited for computing approximate answers in polynomial time.

Drone based terrorist attacks are increasing daily. It is not expected to be long before drones are used to carry out terror attacks in urban areas. We have developed the DUCK multi-agent testbed that security agencies can use to simulate drone-based attacks by diverse actors and develop a combination of surveillance camera, drone, and cyber defenses against them.

Inconsistency-tolerant semantics have been proposed to provide meaningful ontological query answers even in the presence of inconsistencies. Several such semantics rely on the notion of a repair, which is a "maximal" consistent subset of the database, where different maximality criteria might be adopted depending on the application at hand. Previous work in the context of Datalog+/- has considered only the subset and cardinality maximality criteria. We take here a step further and study inconsistency-tolerant semantics under maximality criteria based on weights and priority levels. We provide a thorough complexity analysis for a wide range of existential rule languages and for several complexity measures.

We define and investigate new inconsistency measures that are particularly suitable for dealing with inconsistent spatio-temporal information, as they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions, and thus define ``dimension-aware'' counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

Inconsistency-tolerant semantics have been proposed to provide meaningful query answers even in the presence of inconsistent knowledge. Recently, explainability has also become a prominent problem in different areas of AI. While the complexity of inconsistency-tolerant semantics is rather well-understood, not much attention has been paid yet to the problem of explaining query answers when inconsistencies may exist. Recent work on existential rules in the inconsistent setting has focused only on understanding why a query is entailed. In this paper, we address another important problem, which is explaining why a query is not entailed under an inconsistency-tolerant semantics. In particular, we consider three popular semantics, namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs. We provide a thorough complexity analysis for a wide range of existential rule languages and for several complexity measures.

Past research has shown that over 8 months may elapse between the time when a network is compromised and the time the attack is discovered. During this long gap, attackers can steal valuable intellectual property from the victim. The recent FORGE system [8] has suggested that automatically generating fake—but believable—versions of documents can delay the attacker, cost him money, and increase his uncertainty. However, in order to generate fakes, FORGE only modifies the textual component of the document in question. But in the real world, documents consist of many non-textual components such as charts, equations, formulas, diagrams, and tables. We propose the concept of a Probabilistic Logic Graph (PLG) and show that PLGs provide a single, unified framework within which the different parts of a document can be expressed. We then define the problem of generating, for a given PLG representation of a document, a set of fake yet highly believable PLGs (i.e., documents), so that an attacker looking at them (both the original and the fake ones) cannot easily identify the original document. We show that the problem of generating fake PLGs is intractable—but we propose an approximation algorithm that solves it efficiently. We evaluate the use of PLGs over a corpus of patents and show that our fakes can effectively deceive an adversary.

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.

The problem of managing spatio-temporal data arises in many applications, such as location-based services, environmental monitoring, geographic information systems, and many others. Often spatio-temporal data arising from such applications turn out to be inconsistent, i.e., representing an impossible situation in the real world. Though several inconsistency measures have been proposed to quantify in a principled way inconsistency in propositional knowledge bases, little effort has been done so far on inconsistency measures tailored for the spatio-temporal setting. In this paper, we define and investigate new measures that are particularly suitable for dealing with inconsistent spatio-temporal information, because they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions and thus define “dimension-aware” counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

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.

Consistent query answering is a principled approach for querying inconsistent databases. It relies on two basic notions: the notion of a repair, that is, a consistent database that "minimally" differs from the original one, and the notion of a consistent query answer, that is, a query answer that can be derived from every repair. In general, an inconsistent database can admit multiple repairs, each corresponding to a different way of restoring consistency, and the consistent query answering framework does not make any discrimination among them. However, in many applications it is natural and desired to express preferences among the different choices that can be made to resolve inconsistency.

Query answering over inconsistent knowledge bases is a problem that has attracted a great deal of interest over the years. Different inconsistency-tolerant semantics have been proposed, and most of them are based on the notion of repair, that is, a "maximal" consistent subset of the database. In general, there can be several repairs, so it is often natural and desirable to express preferences among them. In this paper, we propose a framework for querying inconsistent knowledge bases under user preferences for existential rule languages. We provide generalizations of popular inconsistency-tolerant semantics taking preferences into account and study the data and combined complexity of different relevant problems.

Ontology-mediated query answering is an extensively studied paradigm, where the conceptual knowledge provided by an ontology is leveraged towards more enhanced querying of data sources. A major advantage of ontological reasoning is its interpretability, which allows one to derive explanations for query answers. Indeed, explanations have a long history in knowledge representation, and have also been investigated for ontology languages based on description logics and existential rules. Existing works on existential rules, however, merely focus on understanding why a query is entailed, i.e., explaining positive query answers. In this paper, we continue this line of research and address another important problem, namely, explaining why a query is not entailed under existential rules, i.e., explaining negative query answers. We consider various problems related to explaining non-entailments from the abduction literature, and also introduce new problems. For all considered problems, we give a detailed complexity analysis for a wide range of existential rule languages and complexity measures.

Incomplete information arises in many database applications, such as data integration, data exchange, inconsistency management, data cleaning, ontological reasoning, and many others. A principled way of answering queries over incomplete databases is to compute certain answers, which are query answers that can be obtained from every complete database represented by an incomplete one.

Consistent query answering is a principled approach for querying inconsistent knowledge bases. It relies on the notion of a "repair", that is, a maximal consistent subset of the facts in the knowledge base. One drawback of this approach is that entire facts are deleted to resolve inconsistency, even if they may still contain useful "reliable" information. To overcome this limitation, we propose a new notion of repair allowing values within facts to be updated for restoring consistency. This more fine-grained repair primitive allows us to preserve more information in the knowledge base. We also introduce the notion of a "universal repair", which is a compact representation of all repairs. Then, we show that consistent query answering in our framework is intractable (coNP-complete). In light of this result, we develop a polynomial time approximation algorithm for computing a sound (but possibly incomplete) set of consistent query answers.

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.

Incomplete information arises in many current database applications. Certain answers are a widely accepted semantics of query answering over incomplete databases. Since their computation is a coNP-hard problem, recent research has focused on developing polynomial time approximation algorithms computing a sound (but possibly incomplete) set of certain answers. In this demo we showcase ACID, a system to compute sound sets of certain answers. The central tools of its underlying algorithms are conditional tables and the conditional evaluation of relation algebra. Different evaluation strategies can be applied, with more accurate ones having higher complexity, but returning more certain answers. We show how to query incomplete databases using the ACID system, which offers a suite of approximation algorithms enabling users to choose the technique that best meets their needs in terms of balance between efficiency and quality of the result's approximation.

Computing shortest distances is a central task in many domains. The growing number of applications dealing with dynamic graphs calls for incremental algorithms, as it is impractical to recompute shortest distances from scratch every time updates occur. In this paper, we address the problem of maintaining all-pairs shortest distances in dynamic graphs. We propose efficient incremental algorithms to process sequences of edge deletions/insertions/updates and vertex deletions/insertions. The proposed approach relies on some general operators that can be easily “instantiated” both in main memory and on top of different underlying DBMSs. We provide complexity analyses of the proposed algorithms. Experimental results on several real-world datasets show that current main-memory algorithms become soon impractical, disk-based ones are needed for larger graphs, and our approach significantly outperforms state-of-the-art algorithms.

Computing shortest distances is a central task in many graph applications. Although many algorithms to solve this problem have been proposed, they are designed to work in the main memory and/or with static graphs, which limits their applicability to many current applications where graphs are subject to frequent updates. In this paper, we propose novel efficient incremental algorithms for maintaining all-pairs shortest distances in dynamic graphs. We experimentally evaluate our approach on real-world datasets, showing that it outperforms current algorithms designed for the same problem.

Computing shortest distances is a central task in many graph applications. Since it is impractical to recompute shortest distances from scratch every time the graph changes, many algorithms have been proposed to incrementally maintain shortest distances after edge deletions or insertions.

The chase is a well-known algorithm with a wide range of applications in data exchange, data cleaning, data integration, query optimization, and ontological reasoning. Since the chase evaluation might not terminate and it is undecidable whether it terminates, the problem of defining (decidable) sufficient conditions ensuring termination has received a great deal of interest in recent years. In this regard, several termination criteria have been proposed. One of the main weaknesses of current approaches is the limited analysis they perform on equality generating dependencies (EGDs). In this paper, we propose sufficient conditions ensuring that a set of dependencies has at least one terminating chase sequence. We propose novel criteria which are able to perform a more accurate analysis of EGDs. Specifically, we propose a new stratification criterion and an adornment algorithm. The latter can both be used as a termination criterion and be combined with current techniques to make them more effective, in that strictly more sets of dependencies are identified. Our techniques identify sets of dependencies that are not recognized by any of the current criteria.

Abstract It is widely acknowledged that function symbols are an important feature in answer set programming, as they make modelling easier, increase the expressive power, and allow us to deal with infinite domains. The main issue with their introduction is that the evaluation of a program might not terminate and checking whether it terminates or not is undecidable. To cope with this problem, several classes of logic programs have been proposed where the use of function symbols is restricted but the program evaluation termination is guaranteed. Despite the significant body of work in this area, current approaches do not include many simple practical programs whose evaluation terminates. In this paper, we present the novel classes ofrule-boundedandcycle-bounded programs, which overcome different limitations of current approaches by performing a more global analysis of how terms are propagated from the body to the head of rules. Results on the correctness, the complexity, and the expressivity of the proposed approach are provided.

There are numerous applications where we wish to discover unexpected activities in a sequence of time-stamped observation data--for instance, we may want to detect inexplicable events in transactions at a website or in video of an airport tarmac. In this paper, we start with a known set $({\cal A})$ of activities (both innocuous and dangerous) that we wish to monitor. However, in addition, we wish to identify "unexplained" subsequences in an observation sequence that are poorly explained (e.g., because they may contain occurrences of activities that have never been seen or anticipated before, i.e., they are not in $({\cal A})$). We formally define the probability that a sequence of observations is unexplained (totally or partially) w.r.t. $({\cal A})$. We develop efficient algorithms to identify the top-$(k)$ Totally and partially unexplained sequences w.r.t. $({\cal A})$. These algorithms leverage theorems that enable us to speed up the search for totally/partially unexplained sequences. We describe experiments using real-world video and cyber-security data sets showing that our approach works well in practice in terms of both running time and accuracy.

Given a set A of activities expressed via temporal stochastic automata, and a set O of observations (detections of low level events), we study the problem of identifying instances of activities from A in O. While past work has developed algorithms to solve this problem, in this paper, we develop methods to significantly scale these algorithms. Our PASS architecture consists of three parts: (i) leveraging past work to represent all activities in A via a single “merged” graph, (ii) partitioning the graph into a set of C subgraphs, where (C + 1) is the number of compute nodes in a cluster, and (iii) developing a parallel activity detection algorithm that uses a different compute node in the cluster to intensively process each subgraph. We propose three possible partitioning methods and a parallel activity-search detection (PASS_Detect) algorithm that coordinates computations across nodes in the cluster. We report on experiments showing that our algorithms enable us to handle both large numbers of observations per second as well as large merged graphs. In particular, on a cluster with 9 compute nodes, PASS can reliably handle between 400K and 569K observations per second and merged graphs with as many as 50K vertices.

Annotated Probabilistic Temporal (APT) logic programs are a form of logic programs that allow users to state (or systems to automatically learn) rules of the form “formula G becomes true Δ t time units after formula F became true with ℓ to u % probability.” In this article, we deal with abductive reasoning in APT logic: given an APT logic program Π, a set of formulas H that can be “added” to Π, and a (temporal) goal g , is there a subset S of H such that Π ∪ S is consistent and entails the goal g ? In general, there are many different solutions to the problem and some of them can be highly repetitive, differing only in some unimportant temporal aspects. We propose a compact representation called super-solutions that succinctly represent sets of such solutions. Super-solutions are compact, but lossless representations of sets of such solutions. We study the complexity of existence of basic, super-, and maximal super-solutions as well as check if a set is a solution/super-solution/maximal super-solution. We then leverage a geometric characterization of the problem to suggest a set of pruning strategies and interesting properties that can be leveraged to make the search of basic and super-solutions more efficient. We propose correct sequential algorithms to find solutions and super-solutions. In addition, we develop parallel algorithms to find basic and super-solutions.

There are numerous applications (e.g., video surveillance, fraud detection, cybersecurity) in which we wish to identify unexplained sets of events. Most related past work has been domain-dependent (e.g., video surveillance, cybersecurity) and has focused on the valuable class of statistical anomalies in which statistically unusual events are considered. In contrast, suppose there is a set A of known activity models (both harmless and harmful) and a log L of time-stamped observations. We define a part L '⊆ L of the log to represent an unexplained situation when none of the known activity models can explain L ' with a score exceeding a user-specified threshold. We represent activities via probabilistic penalty graphs (PPGs) and show how a set of PPGs can be combined into one Super-PPG for which we define an index structure. Given a compute cluster of ( K + 1) nodes (one of which is a master node), we show how to split a Super-PPG into K subgraphs, each of which can be independently processed by a compute node. We provide algorithms for the individual compute nodes to ensure seamless handoffs that maximally leverage parallelism. PADUA is domain-independent and can be applied to many domains (perhaps with some specialization). We conducted detailed experiments with PADUA on two real-world datasets—the ITEA CANDELA video surveillance dataset and a network traffic dataset appropriate for cybersecurity applications. PADUA scales extremely well with the number of processors and significantly outperforms past work both in accuracy and time. Thus, PADUA represents the first parallel architecture and algorithm for identifying unexplained situations in observation data, offering both scalability and accuracy.

Most real-world databases have at least some missing data. Today, users of such databases are “on their own” in terms of how they manage this incompleteness. In this paper, we propose the general concept of partial information policy (PIP) operator to handle incompleteness in relational databases. PIP operators build upon preference frameworks for incomplete information, but accommodate different types of incomplete data (e.g., a value exists but is not known; a value does not exist; a value may or may not exist). Different users in the real world have different ways in which they want to handle incompleteness-PIP operators allow them to specify a policy that matches their attitude to risk and their knowledge of the application and how the data was collected. We propose index structures for efficiently evaluating PIP operators and experimentally assess their effectiveness on a real-world airline data set. We also study how relational algebra operators and PIP operators interact with one another.

There has been extensive work in many different fields on how phenomena of interest (e.g., diseases, innovation, product adoption) “diffuse” through a social network. As social networks increasingly become a fabric of society, there is a need to make “optimal” decisions with respect to an observed model of diffusion. For example, in epidemiology, officials want to find a set of k individuals in a social network which, if treated, would minimize spread of a disease. In marketing, campaign managers try to identify a set of k customers that, if given a free sample, would generate maximal “buzz” about the product. In this article, we first show that the well-known Generalized Annotated Program (GAP) paradigm can be used to express many existing diffusion models. We then define a class of problems called Social Network Diffusion Optimization Problems (SNDOPs). SNDOPs have four parts: (i) a diffusion model expressed as a GAP, (ii) an objective function we want to optimize with respect to a given diffusion model, (iii) an integer k > 0 describing resources (e.g., medication) that can be placed at nodes, (iv) a logical condition VC that governs which nodes can have a resource (e.g., only children above the age of 5 can be treated with a given medication). We study the computational complexity of SNDOPs and show both NP-completeness results as well as results on complexity of approximation. We then develop an exact and a heuristic algorithm to solve a large class of SNDOPproblems and show that our GREEDY-SNDOPs algorithm achieves the best possible approximation ratio that a polynomial algorithm can achieve (unless P = NP ). We conclude with a prototype experimental implementation to solve SNDOPs that looks at a real-world Wikipedia dataset consisting of over 103,000 edges.

Abstract Recent years have witnessed an increasing interest in enhancing answer set solvers by allowing function symbols. Since the introduction of function symbols makes common inference tasks undecidable, research has focused on identifying classes of programs allowing only a restricted use of function symbols while ensuring decidability of common inference tasks. Finitely-ground programs, introduced in Calimeri et al. (2008), are guaranteed to admit a finite number of stable models with each of them of finite size. Stable models of such programs can be computed and thus common inference tasks become decidable. Unfortunately, checking whether a program is finitely-ground is semi-decidable. This has led to several decidable criteria, called termination criteria, providing sufficient conditions for a program to be finitely-ground. This paper presents a new technique that, used in conjunction with current termination criteria, allows us to detect more programs as finitely-ground. Specifically, the proposed technique takes a logic program ${\cal P}$ and transforms it into an adorned program ${{\cal P}}$ μ with the aim of applying termination criteria to ${{\cal P}}$ μ rather than ${\cal P}$ . The transformation is sound in that if the adorned program satisfies a certain termination criterion, then the original program is finitely-ground. Importantly, applying termination criteria to adorned programs rather than the original ones strictly enlarges the class of programs recognized as finitely-ground.

Though centrality of vertices in social networks has been extensively studied, all past efforts assume that centrality of a vertex solely depends on the structural properties of graphs. However, with the emergence of online "semantic" social networks where vertices have properties (e.g. gender, age, and other demographic data) and edges are labeled with relationships (e.g. friend, follows) and weights (measuring the strength of a relationship), it is essential that we take semantics into account when measuring centrality. Moreover, the centrality of a vertex should be tied to a diffusive property in the network - a Twitter vertex may have high centrality w.r.t. jazz, but low centrality w.r.t. Republican politics. In this paper, we propose a new notion of diffusion centrality (DC) in which semantic aspects of the graph, as well as a diffusion model of how a diffusive property p is spreading, are used to characterize the centrality of vertices. We present a hyper graph based algorithm to compute DC and report on a prototype implementation and experiments showing how we can compute DCs (using real YouTube data) on social networks in a reasonable amount of time. We compare DC with classical centrality measures like degree, closeness, betweenness, eigenvector and stress centrality and show that in all cases, DC produces higher quality results. DC is also often faster to compute than both betweenness, closeness and stress centrality, but slower than degree and eigenvector centrality.

Consider a video surveillance application that monitors some location. The application knows a set of activity models (that are either normal or abnormal or both), but in addition, the application wants to find video segments that are unexplained by any of the known activity models - these unexplained video segments may correspond to activities for which no previous activity model existed. In this paper, we formally define what it means for a given video segment to be unexplained (totally or partially) w.r.t. a given set of activity models and a probability threshold. We develop two algorithms - FindTUA and FindPUA - to identify Totally and Partially Unexplained Activities respectively, and show that both algorithms use important pruning methods. We report on experiments with a prototype implementation showing that the algorithms both run efficiently and are accurate.

Abstract This paper presents a logic language for expressing search and optimization problems. Specifically, first a language obtained by extending (positive) DATALOG with intuitive and efficient constructs (namely, stratified negation, constraints, and exclusive disjunction) is introduced. Next, a further restricted language only using a restricted form of disjunction to define (nondeterministically) subsets (or partitions) of relations is investigated. This language, called atalog, captures the power of DATALOG¬ in expressing search and optimization problems. A system prototype implementing atalog is presented. The system translates atalog queries into Optimization Programming Language (OPL) programs which are executed by the ILOG OPL Development Studio. Our proposal combines easy formulation of problems, expressed by means of a declarative logic language, with the efficiency of the ILOG System. Several experiments show the effectiveness of this approach.

The paper proposes a logic framework for modeling the interaction among deductive databases and computing consistent answers to logic queries in a P2P environment. As usual, data are exchanged among peers by using logical rules, called mapping rules. The novelty of our approach is that only data not violating integrity constraints are exchanged. The (declarative) semantics of a P2P system is defined in terms of weak models. Under this semantics only facts not making the local databases inconsistent can be imported, and the preferred weak models are the consistent scenarios in which peers import maximal sets of facts not violating integrity constraints. A characterization of the preferred weak model semantics, allowing to model a P2P system with a prioritized logic program, is provided. The proposed framework is then extended in order to also take into account P2P system in which each peer may be locally inconsistent, i.e. its data does not satisfy some of its constraints. Finally, the complexity of P2P logic queries is investigated