We address the context of Single-Audience Value-Based Abstract Argumentation Framework (AVAF), where the arguments are labeled with the social values that they promote and the activation/deactivation of the attacks depends on the audience profile (expressed as a set of preferences between the social values). Herein, we introduce a new notion of robustness for measuring the sensitivity of the outcome of the reasoning to the extent of changes in the audience profile. In particular, for a set of arguments S or a single argument a, we define the robustness degree of the status of S or a as the maximum number k* of deletions/insertions of preferences from/into the audience profile that are tolerable, in the sense that S remains an extension (or a non-extension) or a accepted (or unaccepted) after performing at most k* deletions/insertions. We introduce the decision problems related to the computation of the robustness degree and focus on thoroughly investigating their computational complexity.

We present ACME: A Chatbot for asylum-seeking Migrants in Europe. ACME relies on computational argumentation and aims to help migrants identify the highest level of protection they can apply for. This would contribute to a more sustainable migration by reducing the load on territorial commissions, Courts, and humanitarian organizations supporting asylum applicants. We describe the background context, system architecture, underlying technologies, and a case study used to validate the tool with domain experts.

We introduce Incomplete Bipolar Argumentation Frameworks (iBAFs), the extension of Dung’s Abstract Argumentation Frameworks (AAFs) allowing the simultaneous presence of supports (borrowed from BAFs – Bipolar AAFs) and of uncertain elements of the argumentation graph (borrowed from iAAFs – incomplete AAFs). We investigate the computational complexity of verification problem (under the possible perspective) and the acceptance problem, by studying its sensitivity to the semantics of supports and the semantics of extensions. On the one hand, we show that adding supports on top of incompleteness does not affect the complexity of the acceptance. On the other hand, surprisingly, we show that the joint use of bipolarity and incompleteness has a deep impact on the complexity of the verification: for the semantics under which the verification over AAFs is polynomial-time solvable, although moving from AAFs to BAFs or to iAAFs does not change the complexity, the complexity of the verification over iBAFs may increase up to NP-complete.

We propose a new paradigm for reasoning over abstract argumentation frameworks where the “who said what” relation, associating each argument with the set of agents who claimed it, is taken into account, along with possible information on the trustworthiness of the agents. Specifically, we extend the traditional reasoning based on the classical verification and acceptance problems and introduce a reasoning paradigm investigating how the “robustness” of a set of arguments S (in terms of being an extension or not) or of an argument a (in terms of being accepted or not) can change if what has been claimed by some agents is ignored (as if these agents were removed from the dispute modeled by the argumentation framework). In this regard, we address the problems of searching the “minimum extent” of the removal of agents that makes a set S an extension or an argument a accepted. Compared with the case where only the “yes/no” answer of the traditional verification and acceptance problems are available, the knowledge of such a minimum provides the analyst with further insights allowing them to better judge the robustness of S and a. We consider the above minimization problems in two variants, where the agents are associated with a measure of their trustworthiness or not and provide a thorough characterization of their complexities.

In the context of probabilistic AAFs, we intro- duce AAFs with marginal probabilities (mAAFs) requiring only marginal probabilities of argu- ments/attacks to be specified and not relying on the independence assumption. Reasoning over mAAFs requires taking into account multiple probability distributions over the possible worlds, so that the probability of extensions is not determined by a unique value, but by an interval. We focus on the problems of computing the max and min probabil- ities of extensions over mAAFs under Dung’s se- mantics, characterize their complexity, and provide closed formulas for polynomial cases.

We introduce "argument-incomplete Abstract Argumentation Frameworks with dependencies", that extend the traditional abstract argumentation reasoning to the case where some arguments are uncertain and correlated through logical dependencies (such as mutual exclusion, implication, etc.). We characterize the complexities of the problems DSAT of deciding the satisfiability of the dependencies and PDVER of verifying extensions, and show how they depend on the forms of dependencies and, for PDVER, also on the semantics of the extensions.

Attack-Incomplete Abstract Argumentation Frameworks (att- iAAFs) are a popular extension of AAFs where attacks are marked as uncertain when they are not unanimously per- ceived by different agents reasoning on the same arguments. We here extend att-iAAFs with the possibility of specifying correlations involving the uncertain attacks. This feature sup- ports a unified and more precise representation of the differ- ent scenarios for the argumentation, where, for instance, it can be stated that an attack α has to be considered only if an attack β is considered, or that α and β are alternative, and so on. In order to provide a user-friendly language for spec- ifying the correlations, we allow the argumentation analyst to express them in terms of a set of elementary dependen- cies, using common logical operators (namely, OR , NAND , CHOICE , ⇒). In this context, we focus on the problem of verifying extensions under the possible perspective, and study the sensitivity of its computational complexity to the forms of correlations expressed and the semantics of the extensions.

We revisit the notion of i-extension, i.e., the adaption of the fundamental notion of extension to the case of incomplete Abstract Argumentation Frameworks. We show that the definition of i-extension raises some concerns in the "possible" variant, e.g., it allows even conflicting arguments to be collectively considered as members of an (i-)extension. Thus, we introduce the alternative notion of i*-extension overcoming the highlighted problems, and provide a thorough complexity characterization of the corresponding verification problem. Interestingly, we show that the revisitation not only has beneficial effects for the semantics, but also for the complexity: under various semantics, the verification problem under the possible perspective moves from NP-complete to P.

Digital content piracy is nowadays really burden-some both for companies and professionals. To overcome this problem, digital data producers usually protect their documents from illegal distributions by leveraging digital fingerprinting techniques for marking each copy of their documents in order to uniquely identify it. Unfortunately, in the case that multiple malicious users jointly collaborate for illegally sharing a document copy, they may forge the embedded fingerprint by simply comparing their copies and modifying the fingerprint's bits that differ in their copies. In [1] an optimal fingerprinting schema has been defined for accusing a guilty user with very high probability under the assumption that the fingerprinting code is sufficiently long. To remove this assumption, several joint-decoding techniques have been recently proposed [2], [3]. In this work, we perform a deep experimental analysis of the Metropolis-Hastings based joint-decoding approach defined in [3], with the aim of assessing the sensitivity to various parameters of the model, thus making it usable in practical contexts.

The complexity of the probabilistic counterparts of the verification and acceptance problems is investigated over probabilistic Abstract Argumentation Frameworks (prAAFs), in a setting more general than the literature, where the complexity has been characterized only under independence between arguments/defeats. The complexity of these problems is shown to depend on the semantics of the extensions, the way of encoding the prAAF, and the correlations between arguments/defeats. In this regard, in order to study the impact of different correlations between arguments/defeats on the complexity, a new form of prAAF is introduced, called gen. It is based on the well-known paradigm of world-set sets, and it allows the correlations to be easily distinguishable.

Probabilistic Bipolar Abstract Argumentation Frameworks (prBAFs), combining the possibility of specifying supports between arguments with a probabilistic modeling of the uncertainty, are considered, and the complexity of the fundamentalproblem of computing extensions' probabilities is addressed.The most popular semantics of supports and extensions are considered, as well as different paradigms for defining the probabilistic encoding of the uncertainty.Interestingly, the presence of supports, which does not alter the complexity of verifying extensions in the deterministic case, is shown to introduce a new source of complexity in some probabilistic settings, for which tractable cases are also identified.

research-article Share on WFinger: a joint-decoder for very short Tardos fingerprinting codes Authors: Bettina Fazzinga ICAR-CNR, Rende (CS), Italy ICAR-CNR, Rende (CS), ItalyView Profile , Sergio Flesca DIMES, University of Calabria, Rende (CS), Italy DIMES, University of Calabria, Rende (CS), ItalyView Profile , Filippo Furfaro DIMES, University of Calabria, Rende (CS), Italy DIMES, University of Calabria, Rende (CS), ItalyView Profile , Elio Masciari ICAR-CNR, Rende (CS), Italy ICAR-CNR, Rende (CS), ItalyView Profile Authors Info & Claims IDEAS '17: Proceedings of the 21st International Database Engineering & Applications SymposiumJuly 2017 Pages 176–183https://doi.org/10.1145/3105831.3105860Published:12 July 2017Publication History 1citation36DownloadsMetricsTotal Citations1Total Downloads36Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We characterize the complexity of the problem of computing the probabilities of the extensions in probabilistic abstract argumentation. We consider all the most popular semantics of extensions (admissible, stable, preferred, complete, grounded, ideal-set, ideal and semi-stable) and different forms of correlations that can be defined between arguments and defeats. We show that the complexity of the problem ranges from FP to FP#P-complete, with FP||NP-complete cases, depending on the semantics of the extensions and the imposed correlations.

Log analysis and querying recently received a renewed interest from the research community, as the effective understanding of process behavior is crucial for improving business process management. Indeed, currently available log querying tools are not completely satisfactory, especially from the viewpoint of easiness of use. As a matter of fact, there is no framework which meets the requirements of easiness of use, flexibility and efficiency of query evaluation. In this paper, we propose a framework for graphical querying of (process) log data that makes the log analysis task quite easy and efficient, adopting a very general model of process log data which guarantees a high level of flexibility. We implemented our framework by using a flexible storage architecture and a user-friendly data analysis interface, based on an intuitive and yet expressive graph-based query language. Experiments performed on real data confirm the validity of the approach.

Big data paradigm is currently the leading paradigm for data production and management. As a matter of fact, new information are generated at high rates in specialized fields (e.g., cybersecurity scenario). This may cause that the events to be studied occur at rates that are too fast to be effectively analyzed in real time. For example, in order to detect possible security threats, millions of records in a high-speed flow stream must be screened. To ameliorate this problem, a viable solution is the use of data compression for reducing the amount of data to be analyzed. In this paper we propose the use of privacy-preserving histograms, that provide approximate answers to 'safe' queries, for analyzing data in the cybersecurity scenario without compromising individuals' privacy, and we describe our system that has been used in a real life scenario.

A probabilistic framework for cleaning the data collected by Radio-Frequency IDentification (RFID) tracking systems is introduced. What has to be cleaned is the set of trajectories that are the possible interpretations of the readings: a trajectory in this set is a sequence whose generic element is a location covered by the reader(s) that made the detection at the corresponding time point. The cleaning is guided by integrity constraints and consists of discarding the inconsistent trajectories and assigning to the others a suitable probability of being the actual one. The probabilities are evaluated by adopting probabilistic conditioning that logically consists of the following steps. First, the trajectories are assigned a priori probabilities that rely on the independence assumption between the time points. Then, these probabilities are revised according to the spatio-temporal correlations encoded by the constraints. This is done by conditioning the a priori probability of each trajectory to the event that the constraints are satisfied: this means taking the ratio of this a priori probability to the sum of the a priori probabilities of all the consistent trajectories. Instead of performing these steps by materializing all the trajectories and their a priori probabilities (which is infeasible, owing to the typically huge number of trajectories), our approach exploits a data structure called conditioned trajectory graph (ct-graph) that compactly represents the trajectories and their conditioned probabilities, and an algorithm for efficiently constructing the ct-graph, which progressively builds it while avoiding the construction of components encoding inconsistent trajectories.

The increasing availability of large process log repositories calls for efficient solutions for their analysis. In this regard, a novel specialized compression technique for process logs is proposed, that builds a synopsis supporting a fast estimation of aggregate queries, which are of crucial importance in exploratory and high-level analysis tasks. The synopsis is constructed by progressively merging the original log-tuples, which represent single activity executions within the process instances, into aggregate tuples, summarizing sets of activity executions. The compression strategy is guided by a heuristic aiming at limiting the loss of information caused by summarization, while guaranteeing that no information is lost on the set of activities performed within the process instances and on the order among their executions. The selection conditions in an aggregate query are specified in terms of a graph pattern, that allows precedence relationships over activity executions to be expressed, along with conditions on their starting times, durations, and executors. The efficacy of the compression technique, in terms of capability of reducing the size of the log and of accuracy of the estimates retrieved from the synopsis, has been experimentally validated.

A probabilistic framework is introduced for reducing the inherent uncertainty of trajectory data collected for RFID-monitored ob-jects. The framework represents the position of an object at each instant as a random variable over the set of possible locations. The probability density function of this random variable is initialized according to an a-priori probability distribution, and then revised by conditioning it w.r.t. the event that integrity constraints are sat-isfied. In particular, integrity constraints implied by the structure of the map of locations and the motility characteristics (such as the maximum speed) of the monitored objects are exploited (namely, direct unreachability, latency and minimum traveling time constraints). The efficiency and effectiveness of the proposed approach are as-sessed experimentally on synthetic data. 1.

An offline cleaning technique is proposed for translating the readings generated by RFID-tracked moving objects into positions over a map. It consists in a grid-based two-way filtering scheme embedding a sampling strategy for addressing missing detections. The readings are first processed in time order: at each time point t, the positions (i.e., cells of a grid assumed over the map) compatible with the reading at t are filtered according to their reachability from the positions that survived the filtering for the previous time point. Then, the positions that survived the first filtering are re-filtered, applying the same scheme in inverse order. As the two phases proceed, a probability is progressively evaluated for each candidate position at each time point t: at the end, this probability assembles the three probabilities of being the actual position given the past and future positions, and given the reading at t. A sampling procedure is employed at certain steps of the first filtering phase to intelligently reduce the number of cells to be considered as candidate positions at the next steps, as their number can grow dramatically in the presence of consecutive missing detections. The proposed approach is experimentally validated and shown to be efficient and effective in accomplishing its task.

RFID-based systems for object tracking and supply chain management have been emerging since the RFID technology proved effective in monitoring movements of objects. The monitoring activity typically results in huge numbers of readings, thus making the problem of efficiently retrieving aggregate information from the collected data a challenging issue. In fact, tackling this problem is of crucial importance, as fast answers to aggregate queries are often mandatory to support the decision making process. In this regard, a compression technique for RFID data is proposed, and used as the core of a system supporting the efficient estimation of aggregate queries. Specifically, this technique aims at constructing a lossy synopsis of the data over which aggregate queries can be estimated, without accessing the original data. Owing to the lossy nature of the compression, query estimates are approximate, and are returned along with intervals that are guaranteed to contain the exact query answers. The effectiveness of the proposed approach has been experimentally validated, showing a remarkable trade-off between the efficiency and the accuracy of the query estimation.

Query relaxation is the process of weakening a query to a more general one, and it is frequently employed to support approximate query answering. In this paper, rewriting systems for a wide fragment of XPath are investigated, which accomplish query relaxation through the application of simple rewriting rules transforming navigational axes and node tests into relaxed ones. Specifically, a general yet simple form of rewriting rules is considered, which subsumes the forms adopted in several rewriting systems for approximate XPath query answering. The expressiveness of rewriting systems based on this form of rules is characterized in terms of their capability of transforming a query into every more general formulation. It is shown that traditional rewriting systems are not only incomplete w.r.t. containment, but also w.r.t. the stricter form known as containment by homomorphism. This limitation is overcome by defining a set R* of rewriting rules which are still of the same simple form of traditional ones, but are expressive enough to catch at least containment by homomorphism. Then, an algorithm is proposed which exploits R* to provide approximate answers of queries along with a measure of their approximation degree.

The problem of defining suitable rewriting mechanisms for XML query languages to support approximate query answering has received a great deal of attention in the last few years, owing to its practical impact in several scenarios. For instance, in the typical scenario of distributed XML data without a shared data scheme, accomplishing the extraction of the information of interest often requires queries to be rewritten into relaxed ones, in order to adapt them to the schemes adopted in the different sources.In this paper, rewriting systems for a wide fragment of XPath (which is the core of several languages for manipulating XML data) are investigated, and a general form of rewriting rules (namely, generalization rules) is considered, which subsumes the forms adopted in the most well-known rewriting systems. Specifically, the expressiveness of rewriting systems based on this form of rules is characterized: on the one hand, it is shown that rewriting systems based on generalization rules are incomplete w.r.t. containment (thus, traditional rewriting mechanisms do not suffice to rewrite a query into any more general one). On the other hand, it is also shown that the expressiveness of state-of-the-art rewriting systems can be improved by employing rewriting primitives as simple as those traditionally used, which enable any query to be relaxed into every more general one related to it via homomorphism.

A P2P-based framework supporting the extraction of aggregates from historical multidimensional data is proposed, which provides efficient and robust query evaluation. When a data population is published, data are summarized in a synopsis, consisting of an index built on top of a set of subsynopses (storing compressed representations of distinct data portions). The index and the subsynopses are distributed across the network, and suitable replication mechanisms taking into account the query workload and network conditions are employed that provide the appropriate coverage for both the index and the subsynopses.

The problem of extracting consistent information from relational databases violating integrity constraints on numerical data is addressed. In particular, aggregate constraints defined as linear inequalities on aggregate-sum queries on input data are considered. The notion of repair as consistent set of updates at attribute-value level is exploited, and the characterization of several data-complexity issues related to repairing data and computing consistent query answers is provided. Moreover, a method for computing “reasonable” repairs of inconsistent numerical databases is provided, for a restricted but expressive class of aggregate constraints. Several experiments are presented which assess the effectiveness of the proposed approach in real-life application scenarios.

Radio Frequency Identification (RFID) applications are emerging as key components in object tracking and supply chain management systems since in the next future almost every major retailer will use RFID systems to track the shipment of products from suppliers to warehouses. Due to the streaming nature of RFID readings, large amounts of data are generated by these devices at high production rates. This phenomenon is even more relevant since RFIDs are so cheap that every individual item can be tagged thus leaving a "trail" of data as it moves across different locations. This scenario raises new challenges in effectively and efficiently exploiting such large amounts of data. In this paper we address the problem of compressing RFID data in order to enable devices with limited amount of available memory (such as PDAs) to issue queries on RFID warehouses. In particular, we designed a lossy strategy for collapsing tuples carrying information about items being delivered at different location of the supply chain.

XPath expressions define navigational queries on XML data and are issued on XML documents to select sets of element nodes. Due to the wide use of XPath, which is embedded into several languages for querying and manipulating XML data, the problem of efficiently answering XPath queries has received increasing attention from the research community. As the efficiency of computing the answer of an XPath query depends on its size, replacing XPath expressions with equivalent ones having the smallest size is a crucial issue in this direction. This article investigates the minimization problem for a wide fragment of XPath (namely X P [✶] ), where the use of the most common operators (child, descendant, wildcard and branching) is allowed with some syntactic restrictions. The examined fragment consists of expressions which have not been specifically studied in the relational setting before: neither are they mere conjunctive queries (as the combination of “//” and “*” enables an implicit form of disjunction to be expressed) nor do they coincide with disjunctive ones (as the latter are more expressive). Three main contributions are provided. The “global minimality” property is shown to hold: the minimization of a given XPath expression can be accomplished by removing pieces of the expression, without having to re-formulate it (as for “general” disjunctive queries). Then, the complexity of the minimization problem is characterized, showing that it is the same as the containment problem. Finally, specific forms of XPath expressions are identified, which can be minimized in polynomial time.

In this paper, we propose a variant of stable model semantics for disjunctive logic programming and deductive databases. The semantics, called minimal founded, generalizes stable model semantics for normal (i.e. non-disjunctive) programs, but differs from disjunctive stable model semantics (the extension of stable model semantics for disjunctive programs). Compared with disjunctive stable model semantics, minimal founded semantics seems to be more intuitive, it gives meaning to programs which are meaningless under stable model semantics and is no harder to compute. More specifically, minimal founded semantics differs from stable model semantics only for disjunctive programs having constraint rules or rules working as constraints. We study the expressive power of the semantics, and show that for general disjunctive datalog programs it has the same power as disjunctive stable model semantics.

The main drawbacks of handheld devices (small storage space, small size of the display screen, discontinuance of the connection to the WLAN, etc.) are often incompatible with the need of querying and browsing information extracted from the enormous amount of data which are accessible through the network. In this application scenario, the issues of compression and summarization of data have a leading role: data in a lossy compressed format can be transmitted more efficiently than original ones, and can be effectively stored in the handheld devices (setting the compression ratio accordingly). In this paper we describe a very effective compression technique for datacubes and the architecture of a system (based on this compression technique), called Hand-OLAP, which allows a handheld device to extract and browse compressed information coming from an OLAP server distributed on a wired network.

In many application contexts, like statistical databases, scientific databases, query optimizers, OLAP, and so on, data are often summarized into synopses of aggregate values. Summarization has the great advantage of saving space, but querying aggregate data rather than the original ones introduces estimation errors which cannot be in general avoided, as summarization is a lossy compression. A central problem in designing summarization techniques is to retain a certain degree of accuracy in reconstructing query answers. In this paper we restrict our attention to two-dimensional data, which are relevant for a number of applications, and propose a hierarchical summarization technique, which is combined with the use of indices, i.e. compact structures providing an approximate description of portions of the original data. Experimental results show that the technique gives approximation errors much smaller than other "general purpose" techniques, such as wavelets and various types of multi-dimensional histogram.

Informally presents the query language /spl Xscr//spl Gscr//spl Lscr/ (eXtensible Graphical Language). The main features of the language are described by means of two queries on a document named "bib.xml" (a document describing the bibliographic details of a book).

In this paper we present a graphical query language for XML. The language, based on a simple form of graph grammars, permits us to extract data and reorganize information in a new structure. As with most of the current query languages for XML, queries consist of two parts: one extracting a sub-graph and one constructing the output graph. The semantics of queries is given in terms of graph grammars. The use of graph grammars makes it possible to define, in a simple way, the structural properties of both the subgraph that has to be extracted and the graph that has to be constructed. By means of examples, we show the effectiveness and simplicity of our approach.