Search

Analyzing and predicting the dynamics of opinion formation in the context of social environments are problems that attracted much attention in literature. While grounded in social psychology, these problems are nowadays popular within the artificial intelligence community, where opinion dynamics are often studied via game-theoretic models in which individuals/agents hold opinions taken from a fixed set of discrete alternatives, and where the goal is to find those configurations where the opinions expressed by the agents emerge as a kind of compromise between their innate opinions and the social pressure they receive from the environments. As a matter of facts, however, these studies are based on very high-level and sometimes simplistic formalizations of the social environments, where the mental state of each individual is typically encoded as a variable taking values from a Boolean domain. To overcome these limitations, the paper proposes a framework generalizing such discrete preference games by modeling the reasoning capabilities of agents in terms of weighted propositional logics. It is shown that the framework easily encodes different kinds of earlier approaches and fits more expressive scenarios populated by conformist and dissenter agents. Problems related to the existence and computation of stable configurations are studied, under different theoretical assumptions on the structural shape of the social interactions and on the class of logic formulas that are allowed. Remarkably, during its trip to identify some relevant tractability islands, the paper devises a novel technical machinery whose significance goes beyond the specific application to analyzing opinion formation and diffusion, since it significantly enlarges the class of Integer Linear Programs that were known to be tractable so far. [ABSTRACT FROM AUTHOR]

Coalition formation is studied in a setting where agents take part to a group decision-making scenario and where their preferences are expressed via weighted propositional logic, in particular by considering formulas consisting of conjunctions of literals only. Interactions among agents are constrained by an underlying social environment and each agent is associated with a specific social factor determining to which extent she prefers staying in a coalition with other agents. In particular, the utilities of the agents depend not only on their absolute preferences but also on the number of "neighbors" occurring with them in the coalition that emerged. Within this setting, the computational complexity of a number of relevant reasoning tasks is studied, by charting a clear picture of the intrinsic difficulty of finding "agreements" among the agents. Specific algorithmic approaches to reason about such social environments are proposed under the utilitarian perspective, where the collective utility of a coalition is the sum of the utilities of the individuals, as well as under the egalitarian perspective, with the goal being to maximize the utility of the least satisfied agent. These algorithms have been implemented and results of experimental activity are discussed, too. [ABSTRACT FROM AUTHOR]

The Italian Association for Artificial Intelligence (AIxIA) was established in 1988 and has the role of increasing the knowledge of Artificial Intelligence (AI) at several levels, by fostering its teaching in schools and universities, and by promoting both theoretical and applied research in the field through seminars, targeted initiatives and sponsorship of events. The 18th International Conference of the Italian Association for Artificial Intelligence (AIxIA 2019) was held in Rende (CS), Italy, from November 19 to November 22, 2019. [Extracted from the article]

The problem of computing optimal solutions to Constraint Satisfaction Problem (CSP) instances parameterized by the size of the objective function is considered, and fixed-parameter polynomial-time algorithms are proposed within the structure-based framework of tree projections. The algorithms compute the desired optimal (or best k ) solutions whenever there exists a tree projection for the given instance; otherwise, the algorithms report that there is no tree-projection. For the case where a tree projection is available, parallel algorithms are also proposed and analyzed. Structural decomposition methods based on acyclic, bounded treewidth, and bounded generalized hypertree-width hypergraphs, extensively considered in the CSP setting, as well as in conjunctive database query evaluation and optimization, are all covered as special cases of the tree projection framework. [ABSTRACT FROM AUTHOR]

Coalition structure generation is the problem of partitioning the agents of a given environment into disjoint and exhaustive coalitions so that the whole available worth is maximized. While this problem has been classically studied in settings where all coalitions are allowed to form, it has been recently reconsidered in the literature moving from the observation that environments often forbid the formation of certain coalitions. By following this latter perspective, a model for coalition structure generation is proposed where constraints of two different kinds can be expressed simultaneously. Indeed, the model is based on the concept of valuation structure , which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems arising in real-world application domains. Then, the complexity of coalition structure generation over valuation structures is studied, by assuming that the functions associating each coalition with its worth are given as input according to some compact encoding—rather than explicitly listing all exponentially-many associations. In particular, islands of tractability are identified based on the topological properties of the underlying interaction graphs and on suitable algebraic properties of the given worth functions. Finally, stability issues over valuation structures are studied too, by considering the core as the prototypical solution concept. [ABSTRACT FROM AUTHOR]

Answering conjunctive queries is a fundamental problem in database theory, and it is equivalent to solving constraint satisfaction problems in artificial intelligence and to other fundamental problems arising in computer science, which can be recast in terms of looking for homomorphisms between relational structures. The problem is NP-hard, so that several research e orts have been made in the literature for identifying tractable classes, known as islands of tractability, as well as for devising clever heuristics for solving efficiently real-world instances. Many heuristic approaches are based on enforcing on the given instance a property called local consistency (also, relational arc-consistency), where each tuple in every query atom matches at least one tuple in every other query atom. Interestingly, for many well-known classes of instances, such as for the acyclic ones, enforcing local consistency is even sufficient to solve the given instance correctly. However, the precise power of such a procedure was unclear, but for some very restricted cases. The paper provides answers to long-standing questions about the precise power of algorithms based on enforcing local consistency. The paper deals with both the general framework of tree projections, where local consistency is enforced among arbitrary views defined over the given database instance, and the specific cases where such views are computed according to the so-called structural decomposition methods, such as generalized hypertree width, component hypertree decompositions, and so on. Moreover, the paper deals with both decision and computation problems, by characterizing those tuples that are correct projections of query answers, which finds application in algorithms for answering queries and solving constraint satisfaction problems. As a relevant special case, the power of algorithms based on enforcing local consistency is characterized over the fundamental and deeply studied class of acyclic conjunctive queries. It turns out that local consistency provides the correct answer to a Boolean acyclic query if, and only if, the query is semantically acyclic. [ABSTRACT FROM AUTHOR]

Most structural decomposition methods can be characterized through hypergraph games that are variations of the Robber and Cops graph game that characterizes the notion of treewidth. Decomposition trees correspond to monotone winning strategies of the cops, where the escape space of the robber on the hypergraph is shrunk monotonically. Cops using non-monotonic strategies are more powerful, but such strategies do not correspond to valid decompositions, in general. The paper provides a general way to exploit the power of non-monotonic strategies, by allowing a “greedy” form of non-monotonicity. It is shown that deciding the existence of a (non-monotone) greedy winning strategy (and compute one, if any) is tractable. Moreover, from greedy strategies we can compute valid decomposition trees efficiently. As a consequence, we are able to add power to structural methods and to obtain larger islands of tractability, such as the one based on the new notion of greedy hypertree decomposition. [ABSTRACT FROM AUTHOR]

In many real-world settings, the structure of the environment constrains the formation of coalitions among agents. These settings can be represented by characteristic function games, also known as coalitional games , equipped with interaction graphs. An interaction graph determines the set of all feasible coalitions, in that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. Our work analyzes stability issues arising in such environments, by focusing on the core as a solution concept, and by considering the coalition structure viewpoint, that is, without assuming that the grand-coalition necessarily forms. The complexity of the coalition structure core is studied over a variety of interaction graph structures of interest, including complete graphs, lines, cycles, trees, and nearly-acyclic graphs (formally, having bounded treewidth). The related stability concepts of the least core and the cost of stability are also studied. Results are derived for the setting of compact coalitional games, i.e., for games that are implicitly described via a compact encoding, and where simple calculations on this encoding are to be performed in order to compute the payoff associated with any coalition. Moreover, specific results are provided for compact games defined via marginal contribution networks , an expressive encoding mechanism that received considerable attention in the last few years. [ABSTRACT FROM AUTHOR]

Abstract: Tree projections provide a mathematical framework that encompasses all the various (purely) structural decomposition methods that have been proposed in the literature to single out classes of nearly-acyclic (hyper)graphs, such as the tree decomposition method, which is the most powerful decomposition method on graphs, and the (generalized) hypertree decomposition method, which is its natural counterpart on arbitrary hypergraphs. The paper analyzes this framework, by focusing in particular on “minimal” tree projections, that is, on tree projections without useless redundancies. First, it is shown that minimal tree projections enjoy a number of properties that are usually required for normal form decompositions in various structural decomposition methods. In particular, they enjoy the same kind of connection properties as (minimal) tree decompositions of graphs, with the result being tight in the light of the negative answer that is provided to the open question about whether they enjoy a slightly stronger notion of connection property, defined to speed-up the computation of hypertree decompositions. Second, it is shown that tree projections admit a natural game-theoretic characterization in terms of the Robber and Captain game. In this game, as for the Robber and Cops game characterizing tree decompositions, the existence of winning strategies implies the existence of monotone ones. As a special case, the Robber and Captain game can be used to characterize the generalized hypertree decomposition method, where such a game-theoretic characterization was missing and asked for. Besides their theoretical interest, these results have immediate algorithmic applications both for the general setting and for structural decomposition methods that can be recast in terms of tree projections. [Copyright &y& Elsevier]

Coalitional games are mathematical models suited to study payoff distribution problems in cooperative scenarios. In abstract terms, a coalitional game can be specified by explicitly listing all possible—in fact, exponentially many—coalitions with their associated distributions. This naïve representation, however, quickly becomes infeasible over games involving many agents, thereby calling for suitable compact representations, that is, encoding mechanisms that (on some specific classes of games of interest) take an amount of space that grows polynomially with the number of agents. To date, a plethora of compact encodings have been already introduced and analyzed from the algorithm and computational viewpoints. Despite their specific technical differences, these encodings typically share the assumption that the utility associated with a coalition can be freely transferred among agents. Indeed, designing encoding mechanisms for the non-transferable utility (NTU) setting is a research issue that has been largely unexplored so far. The paper addresses this issue by proposing a compact encoding for representing and reasoning about the outcomes of NTU coalitional games founding on answer set programming. By exploiting the expressiveness of this well-known knowledge representation formalism, it is shown that the proposed representation can succinctly encode several games of interest within a wide range of application domains. Computational issues arising in the setting have been studied too, by addressing questions related to certain payoff distributions enjoying desirable stability properties. Eventually, a prototype system supporting the proposed framework has been implemented by leveraging a state-of-the-art answer set engine, and results of a thorough experimental activity conducted on top of it have been discussed. [ABSTRACT FROM AUTHOR]

Modeling behavioral aspects of business processes is a hard and costly task, which usually requires heavy intervention of business experts. This explains the increasing attention given to process mining techniques, which automatically extract behavioral process models from log data. In the case of complex processes, however, the models identified by classical process mining techniques are hardly useful to analyze business operations at a suitable abstraction level. In fact, the need of process abstraction emerged in several application scenarios, and abstraction methods are already supported in some business-management platforms, which allow users to manually define abstract views for the process at hand. Therefore, it comes with no surprise that process mining research recently considered the issue of mining processes at different abstraction levels, mainly in the form of a taxonomy of process models, as to overcome the drawbacks of traditional approaches. This paper presents a general framework for the discovery of such a taxonomy, and offers a survey of different kinds of basic techniques that can be exploited to this purpose: (1) workflow modeling and discovery techniques, (2) clustering techniques enabling the discovery of different behavioral process classes, and (3) activity abstraction techniques for associating a generalized process model with each higher level taxonomy node. © 2013 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]

In a great number of applications, it is necessary to distribute resources or tasks to agents collaborating with each other in order to maximize the social welfare of the structure they belong to. The question in these cases is how to divide in a fair way the outcome that the structure eventually earns, say money, to the participating agents. The paper faces this issue by focusing on a real-world application: the distribution of funds to Italian research structures and substructures, after a research assessment program (known as VQR) that is currently evaluating the Italian research production over years 2004-2010. A number of desirable properties for any reasonable fair division rule are identified and exemplified for the case-study application. For instance, it is argued that the money distribution should be independent of possible alternative allocations of research products, and it should consider the actual contribution of every researcher to the outcome of the structure (s)he belongs to. Moreover, the whole process starting from the preliminary phase of products selection is dealt with, in order to prevent possible strategic behaviors from researchers that may lead their structure to miss its best possible score in the evaluation process. A fair solution based on the notion of Shapley value is described and analyzed. It turns out that the proposed solution enjoys all the desirable properties of fair division rules, and it could effectively be implemented in the VQR, as well as in related division-rules applications. [ABSTRACT FROM AUTHOR]

Abstract: Mixed multi-unit combinatorial auctions (MMUCAs) are extensions of classical combinatorial auctions (CAs) where bidders trade transformations of goods rather than just sets of goods. Solving MMUCAs, i.e., determining the sequences of bids to be accepted by the auctioneer, is computationally intractable in general. However, differently from classical combinatorial auctions, little was known about whether polynomial-time solvable classes of MMUCAs can be singled out on the basis of their characteristics. The paper fills this gap, by studying the computational complexity of MMUCA instances under structural and qualitative restrictions, which characterize interactions among bidders and types of bids involved in the various transformations, respectively. [Copyright &y& Elsevier]

Abstract: A prominent goal of process mining is to build automatically a model explaining all the episodes recorded in the log of some transactional system. Whenever the process to be mined is complex and highly-flexible, however, equipping all the traces with just one model might lead to mixing different usage scenarios, thereby resulting in a spaghetti-like process description. This is, in fact, often circumvented by preliminarily applying clustering methods on the process log in order to identify all its hidden variants. In this paper, two relevant problems that arise in the context of applying such methods are addressed, which have received little attention so far: (i) making the clustering aware of outlier traces, and (ii) finding predictive models for clustering results. The first issue impacts on the effectiveness of clustering algorithms, which can indeed be led to confuse real process variants with exceptional behavior or malfunctions. The second issue instead concerns the opportunity of predicting the behavioral class of future process instances, by taking advantage of context-dependent “non-structural” data (e.g., activity executors, parameter values). The paper formalizes and analyzes these two issues and illustrates various mining algorithms to face them. All the algorithms have been implemented and integrated into a system prototype, which has been thoroughly validated over two real-life application scenarios. [Copyright &y& Elsevier]

Abstract: Coalitional games model scenarios where players can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. A fundamental issue of coalitional games is to single out the most desirable outcomes in terms of worth distributions, usually called solution concepts. Since decisions taken by realistic players cannot involve unbounded resources, recent computer science literature advocated the importance of assessing the complexity of computing with solution concepts. In this context, the paper provides a complete picture of the complexity issues arising with three prominent solution concepts for coalitional games with transferable utility, namely, the core, the kernel, and the bargaining set, whenever the game worth-function is represented in some reasonably compact form. The starting points of the investigation are the settings of graph games and of marginal contribution nets, where the worth of any coalition can be computed in polynomial time in the size of the game encoding and for which various open questions were stated in the literature. The paper answers these questions and, in addition, provides new insights on succinctly specified games, by characterizing the computational complexity of the core, the kernel, and the bargaining set in relevant generalizations and specializations of the two settings. Concerning the generalizations, the paper shows that dealing with arbitrary polynomial-time computable worth functions—no matter of the specific game encoding being considered—does not provide any additional source of complexity compared to graph games and marginal contribution nets. Instead, only for the core, a slight increase in complexity is exhibited for classes of games whose worth functions encode NP-hard optimization problems, as in the case of certain combinatorial games. As for specializations, the paper illustrates various tractability results on classes of bounded treewidth graph games and marginal contribution networks. [Copyright &y& Elsevier]

In systems where agents are required to interact with a partially known and dynamic world, sensors can be used to obtain knowledge about the environment. However, sensors may be unreliable, that is, they may deliver wrong information (due, e.g., to hardware or software malfunctioning) and, consequently, they may cause agents to take wrong decisions, which is a scenario that should be avoided. The paper considers the problem of reasoning in noisy environments in a setting where no (either certain or probabilistic) data is available in advance about the reliability of sensors. Therefore, assuming that each agent is equipped with a background theory encoding its general knowledge about the world, a concept of detecting an anomaly perceived in sensor data and the related concept of agent recovering to a coherent status of information are defined. In this context, the complexities of various anomaly detection and anomaly recovery problems are studied. Finally, rewriting algorithms are proposed that transform recovery problems into equivalent inference problems under answer set semantics, thereby making them effectively realizable on top of available answer set solvers. [ABSTRACT FROM AUTHOR]

Abstract: The Constraint Satisfaction Problem (CSP) is a central issue of research in Artificial Intelligence. Due to its intractability, many efforts have been made in order to identify tractable classes of CSP instances, and in fact deep and useful results have already been achieved. In particular, this paper focuses on structural decomposition methods, which are essentially meant to look for near-acyclicity properties of the graphs or hypergraphs that encode the structure of the constraints interactions. In general, constraint scopes comprise an arbitrary number of variables, and thus this structure may be naturally encoded via hypergraphs. However, in many practical applications, decomposition methods are applied over suitable graph representations of the (possibly non-binary) CSP instances at hand. Despite the great interest in such binary approaches, a formal analysis of their power, in terms of their ability of identifying islands of tractability, was missing in the literature. The aim of this paper is precisely to fill this gap, by studying the relationships among binary structural methods, and by providing a clear picture of the tractable fragments of CSP that can be specified with respect to each of these decomposition approaches, when they are applied to binary representations of non-binary CSP instances. In particular, various long-standing questions about primal, dual and incidence graph encodings are answered. The picture is then completed by comparing methods on binary encodings with methods specifically conceived for non-binary constraints. [Copyright &y& Elsevier]

Abstract: A widely accepted rational behavior for non-cooperative players is based on the notion of Nash equilibrium. Although the existence of a Nash equilibrium is guaranteed in the mixed framework (i.e., when players select their actions in a randomized manner) in many real-world applications the existence of “any” equilibrium is not enough. Rather, it is often desirable to single out equilibria satisfying some additional requirements (in order, for instance, to guarantee a minimum payoff to certain players), which we call constrained Nash equilibria. In this paper, a formal framework for specifying these kinds of requirement is introduced and investigated in the context of graphical games, where a player may directly be interested in some of the other players only, called the neighbors of . This setting is very useful for modeling large population games, where typically each player does not directly depend on all the players, and representing her utility function extensively is either inconvenient or infeasible. Based on this framework, the complexity of deciding the existence and of computing constrained equilibria is then investigated, in the light of evidencing how the intrinsic difficulty of these tasks is affected by the requirements prescribed at the equilibrium and by the structure of players’ interactions. The analysis is carried out for the setting of mixed strategies as well as for the setting of pure strategies, i.e., when players are forced to deterministically choose the action to perform. In particular, for this latter case, restrictions on players’ interactions and on constraints are identified, that make the computation of Nash equilibria an easy problem, for which polynomial and highly-parallelizable algorithms are presented. [Copyright &y& Elsevier]

The discovery of information encoded in biological sequences is assuming a prominent role in identifying genetic diseases and in deciphering biological mechanisms. This information is usually encoded in patterns frequently occurring in the sequences, which are also called motifs. In fact, motif discovery has received much attention in the literature, and several algorithms have already been proposed, which are specifically tailored to deal with motifs exhibiting some kinds of "regular structure." Motivated by biological observations, this paper focuses on the mining of loosely structured motifs, i.e., of more general kinds of motif where several "exceptions" may be tolerated in pattern repetitions. To this end, an algorithm exploiting data structures conceived to efficiently handle pattern variabilities is presented and analyzed. Furthermore, a randomized variant with linear time and space complexity is introduced, and a theoretical guarantee on its performances is proven. Both algorithms have been implemented and tested on real data sets. Despite the ability of mining very complex kinds of pattern, performance results evidence a genome-wide applicability of the proposed techniques. [ABSTRACT FROM AUTHOR]

Abstract: Process mining techniques have been receiving great attention in the literature for their ability to automatically support process (re)design. Typically, these techniques discover a concrete workflow schema modelling all possible execution patterns registered in a given log, which can be exploited subsequently to support further-coming enactments. In this paper, an approach to process mining is introduced that extends classical discovery mechanisms by means of an abstraction method aimed at producing a taxonomy of workflow models. The taxonomy is built to capture the process behavior at different levels of detail. Indeed, the most-detailed mined models, i.e., the leafs of the taxonomy, are meant to support the design of concrete workflows, as it happens with existing techniques in the literature. The other models, i.e., non-leaf nodes of the taxonomy, represent instead abstract views over the process behavior that can be used to support advanced monitoring and analysis tasks. All the techniques discussed in the paper have been implemented, tested, and made available as a plugin for a popular process mining framework (ProM). A series of tests, performed on different synthesized and real datasets, evidenced the capability of the approach to characterize the behavior encoded in input logs in a precise and complete way, achieving compelling conformance results even in the presence of complex behavior and noisy data. Moreover, encouraging results have been obtained in a real-life application scenario, where it is shown how the taxonomical view of the process can effectively support an explorative ex-post analysis, hinged on the different kinds of process execution discovered from the logs. [Copyright &y& Elsevier]

Abstract: General patterns of execution that have been frequently scheduled by a workflow management system provide the administrator with previously unknown, and potentially useful information, e.g., about the existence of unexpected causalities between subprocesses of a given workflow. This paper investigates the problem of mining unconnected patterns on the basis of some execution traces, i.e., of detecting sets of activities exhibiting no explicit dependency relationships that are frequently executed together. The problem is faced in the paper by proposing and analyzing two algorithms. One algorithm takes into account information about the structure of the control-flow graph only, while the other is a smart refinement where the knowledge of the frequencies of edges and activities in the traces at hand is also accounted for, by means of a sophisticated graphical analysis. Both algorithms have been implemented and integrated into a system prototype, which may profitably support the enactment phase of the workflow. The correctness of the two algorithms is formally proven, and several experiments are reported to evidence the ability of the graphical analysis to significantly improve the performances, by dramatically pruning the search space of candidate patterns. [Copyright &y& Elsevier]

Abstract: Recently, effective methods model query-answering in data integration systems and inconsistent databases in terms of cautious reasoning over programs under the stable model semantics. Since this task is computationally expensive (co-NP-complete), there is a clear need of suitable techniques for query optimization, in order to make such methods feasible for data-intensive applications. We propose a generalization of the well-known Magic Sets technique to programs with (possibly unstratified) negation under the stable model semantics. Our technique produces a new program whose evaluation is more efficient (due to a smaller instantiation) in general, while preserving full query-equivalence for both brave and cautious reasoning, provided that the original program is consistent. Soundness under cautious reasoning is always guaranteed, even if the original program is inconsistent. In order to formally prove the correctness of our Magic Sets transformation, we introduce a novel notion of modularity for under the stable model semantics, which is more suitable for query answering than previous module definitions. We prove that a query on such a module can be evaluated independently from the rest of the program, while preserving soundness under cautious reasoning. Importantly, for consistent programs, both soundness and completeness are guaranteed for brave reasoning and cautious reasoning. Our Magic Sets optimization constitutes an effective method for enhancing the performance of data integration systems in which query-answering is carried out by means of cautious reasoning over programs. In fact, results of experiments in the EU project INFOMIX, show that Magic Sets are fundamental for the scalability of the system. [Copyright &y& Elsevier]

Abstract: Hypertree width is a measure of the degree of cyclicity of hypergraphs. A number of relevant problems from different areas, e.g., the evaluation of conjunctive queries in database theory or the constraint satisfaction in AI, are tractable when their underlying hypergraphs have bounded hypertree width. However, in practical contexts like the evaluation of database queries, we have more information besides the structure of queries. For instance, we know the number of tuples in relations, the selectivity of attributes and so on. In fact, all commercial query-optimizers are based on quantitative methods and do not care on structural properties. In this paper, in order to combine structural decomposition methods with quantitative approaches, the notion of weighted hypertree decomposition is defined. Weighted hypertree decompositions are equipped with cost functions, that can be used for modeling many situations where there is further information on the given problem, besides its hypergraph representation. The complexity of computing hypertree decompositions having the smallest weights, called minimal hypertree decompositions, is analyzed. It is shown that in many cases tractability is lost if weights are added. However, it is proven that, under some—not very severe—restrictions on the allowed cost functions and on the target hypertrees, optimal weighted hypertree decompositions can be computed in polynomial time. For some easier hypertree weighting functions, this problem is also highly parallelizable. Then, a cost function modeling query evaluation costs is provided, and it is shown how to exploit weighted hypertree decompositions for determining (logical) query plans for answering conjunctive queries. Finally, some preliminary results of an experimental comparison of this query optimization technique with the query optimizer of a commercial DBMS are presented. [Copyright &y& Elsevier]

Process mining techniques have recently received notable attention in the literature for their ability to assist in the (re)design of complex processes by automatically discovering models that explain the events registered in some log traces provided as input. Following this line of research, the paper investigates an extension of such basic approaches, where the identification of different variants for the process is explicitly accounted for, based on the clustering of log traces. Indeed, modeling each group of similar executions with a different schema allows us to single out "conformant" models, which, specifically, minimize the number of modeled enactments that are extraneous to the process semantics. Therefore, a novel process mining framework is introduced and some relevant computational issues are deeply studied. As finding an exact solution to such an enhanced process mining problem is proven to require high computational costs, in most practical cases, a greedy approach is devised. This is founded on an iterative, hierarchical, refinement of the process model, where, at each step, traces sharing similar behavior patterns are clustered together and equipped with a specialized schema. The algorithm guarantees that each refinement leads to an increasingly sound model, thus attaining a monotonic search. Experimental results evidence the validity of the approach with respect to both effectiveness and scalability. [ABSTRACT FROM AUTHOR]

Today's workf low management systems represent a key technological infrastructure for advanced applications that is attracting a growing body of research, mainly focused in developing tools for work flow management, that allow users both to specify the "static" aspects, like preconditions, precedence's among activities, and rules for exception handling, and to control its execution by scheduling the activities on the available resources. This paper deals with an aspect of work lows which has so far not received much attention even though it is crucial for the forthcoming scenarios of large scale applications on the Web: Providing facilities for the human system administrator for identifying the choices performed more frequently in the past that had lead to a desired final configuration. In this context, we formalize the problem of discovering the most frequent patterns of executions, i.e., the work low substructures that have been scheduled more frequently by the system. We attacked the problem by developing two data mining algorithms on the basis of an intuitive and original graph formalization of a work low schema and its occurrences. The model is used both to prove some intractability results that strongly motivate the use of data mining techniques and to derive interesting structural properties for reducing the search space for frequent patterns. Indeed, the experiments we have carried out show that our algorithms outperform standard data mining algorithms adapted to discover frequent patterns of work low executions. [ABSTRACT FROM AUTHOR]

The proliferation of information available on the world wide web and the new emerging technologies that have reduced the barriers in organizing and publishing documents, have made the support for navigation and personalization of web sites an appealing and promising task for the AI community. Making the process of retrieving relevant documents easier is one of the most challenging activities in the design of modern sites and goes beyond any particular domain. This paper proposes a new technique for Web navigation based on current algorithms used in Recommendation Systems. Our approach identifies really relevant documents adopting methodologies similar to those successfully used in current search engines. The effectiveness and the validity of our technique have been shown by several experiments. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of managing inconsistent databases, i.e., databases violating integrity constraints. We propose a general logic framework for computing repairs and consistent answers over inconsistent databases. A repair for a possibly inconsistent database is a minimal set of insert and delete operations which makes the database consistent, whereas a consistent answer is a set of tuples derived from the database, satisfying all integrity constraints, in our framework, different types of rules defining general integrity constraints, repair constraints (i.e., rules defining conditions on the insertion or deletion of atoms), and prioritized constraints (i.e., rules defining priorities among updates and repairs) are considered. We propose a technique based on the rewriting of constraints into (prioritized) extended disjunctive rules with two different forms of negation (negation as failure and classical negation) The disjunctive program can be used for two different purposes: to compute "repairs" for the database and produce consistent answers, i.e., a maximal set of atoms which do not violate the constraints. We show that our technique is sound, complete (each preferred stable model defines a repair and each repair is derived from a preferred stable model), and more general than techniques previously proposed. [ABSTRACT FROM AUTHOR]

Background: The cyclin D1-cyclin dependent kinases (CDK)4/6 inhibitor palbociclib in combination with endocrine therapy shows remarkable efficacy in the management of estrogen receptor (ER)-positive and HER2-negative advanced breast cancer (BC). Nevertheless, resistance to palbociclib frequently arises, highlighting the need to identify new targets toward more comprehensive therapeutic strategies in BC patients. Methods: BC cell lines resistant to palbociclib were generated and used as a model system. Gene silencing techniques and overexpression experiments, real-time PCR, immunoblotting and chromatin immunoprecipitation studies as well as cell viability, colony and 3D spheroid formation assays served to evaluate the involvement of the G protein-coupled estrogen receptor (GPER) in the resistance to palbociclib in BC cells. Molecular docking simulations were also performed to investigate the potential interaction of palbociclib with GPER. Furthermore, BC cells co-cultured with cancer-associated fibroblasts (CAFs) isolated from mammary carcinoma, were used to investigate whether GPER signaling may contribute to functional cell interactions within the tumor microenvironment toward palbociclib resistance. Finally, by bioinformatics analyses and k-means clustering on clinical and expression data of large cohorts of BC patients, the clinical significance of novel mediators of palbociclib resistance was explored. Results: Dissecting the molecular events that characterize ER-positive BC cells resistant to palbociclib, the down-regulation of ERα along with the up-regulation of GPER were found. To evaluate the molecular events involved in the up-regulation of GPER, we determined that the epidermal growth factor receptor (EGFR) interacts with the promoter region of GPER and stimulates its expression toward BC cells resistance to palbociclib treatment. Adding further cues to these data, we ascertained that palbociclib does induce pro-inflammatory transcriptional events via GPER signaling in CAFs. Of note, by performing co-culture assays we demonstrated that GPER contributes to the reduced sensitivity to palbociclib also facilitating the functional interaction between BC cells and main components of the tumor microenvironment named CAFs. Conclusions: Overall, our results provide novel insights on the molecular events through which GPER may contribute to palbociclib resistance in BC cells. Additional investigations are warranted in order to assess whether targeting the GPER-mediated interactions between BC cells and CAFs may be useful in more comprehensive therapeutic approaches of BC resistant to palbociclib. [ABSTRACT FROM AUTHOR]

The paper focuses on cooperative games where the worth of any coalition of agents is determined by the optimal value of a matching problem on (possibly weighted) graphs. These games come in different forms that can be grouped in two broad classes, namely of matching and allocation games, and they have a wide spectrum of applications, ranging from two-sided markets where buyers and sellers are encoded as vertices in a graph, to allocation problems where indivisible goods have to be assigned (matched) to agents in a fair way, possibly using monetary compensations. The Shapley value and the related notion of Banzhaf value have often been identified as appropriate solution concepts for many applications of matching/allocation games, but their computation is intractable in general. It is known that these concepts can be computed in polynomial time for matching games on unweighted trees and on graphs having degree at most two. However, it was open whether or not such positive results could be extended to the more general case of graphs having bounded treewidth, and to the case of allocation problems on weighted graphs. The paper provides a positive answer to these questions, by showing that computing the Shapley value and the Banzhaf value is feasible in polynomial time for the following classes of games: matching games over unweighted graphs having bounded treewidth, allocation games over weighted graphs having bounded treewidth, and allocation games over weighted graphs and such that each good is of interest for two agents at most. Without such structural restrictions, computing these solution concepts on allocation games is instead shown to be #P-hard, even in the case of unweighted graphs. [ABSTRACT FROM AUTHOR]

We consider opinion diffusion on social graphs where agents hold opinions and where social pressure leads them to conform to the opinion manifested by the majority of their neighbors. Within this setting, we look for dynamics that allows us to maximize the diffusion of a target opinion given the initial opinions of all agents. In particular, we focus on the setting where more than two opinions are available to the agents, and we show that the properties of this setting are entirely different from those characterizing the setting where agents hold binary opinions only. Indeed, while it is well-known that greedy dynamics are always optimal ones in the binary case, this is no longer true in our more general setting and—rather surprisingly—even if just three opinions are available. Moreover, while it is possible to decide in polynomial time if a dynamics leading to consensus exists when agents have two available opinions, the problem becomes computationally intractable with three opinions, regardless of the fraction of agents that have the target opinion as their initial opinion. [ABSTRACT FROM AUTHOR]

Radiomics is a quantitative approach to analyzing medical multi-layered images in combination with molecular, genetic and clinical information, which has evidenced very promising results especially in the field of oncology. Radiomics applications, however, pose several challenges from the computational viewpoint, and their effective deployment in real-world scenarios require to carefully put in place a number of sophisticated information fusion algorithms and approaches. The paper overviews some relevant works in this area, by depicting a clear picture of the current trends in information fusion methods defined at the level of the data sources as well as at the level of the models learned for diagnostic purposes. While the potential of radiomics to enhance established diagnostic, prognostic and even therapeutic approaches in different diseases merged rather clearly, the analysis evidences several issues that require to attract further attention in the research community. • Overviews relevant works in Information Fusion (IF) for Radiomics. • Depict current trends in IF methods at data source's level. • Depict current trends in IF methods at model's level focusing on federated learning. • Sort out challenges future research directions of information fusion for Radiomics [ABSTRACT FROM AUTHOR]

The high-order coclustering problem, i.e., the problem of simultaneously clustering heterogeneous types of domain, has become an active research area in the last few years, due to the notable impact it has on several application scenarios. This problem is generally faced by optimizing a weighted combination of functions measuring the quality of coclustering over each pair of domains, where weights are chosen based on the supposed reliability/relevance of their correlation. However, little knowledge is likely to be available, in practice, in order to set these weights in a definite and precise manner. And, more importantly, it might even be conceptually unclear whether to prefer a weighing scheme over others, in those cases where functions encode contrasting goals so that improving the quality for a pair of domains leads to a deterioration for other pairs. The aim of this paper is precisely to shed light on the impact of weighting schemes on techniques based on linear combinations of pairwise objective functions, and to define an approach that overcomes the above problems by looking for an agreement—intuitively, a kind of compromise—among the various domains, thereby getting rid of the need to define an appropriate weighting scheme. Two algorithms performing coclustering on "star-structured” domains, based on linear combinations and agreements, respectively, have been designed within an information-theoretic framework. Results from a thorough experimentation, on both synthetic and real data, are discussed, in order to assess the effectiveness of the approaches and to get more insight into their actual behavior. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper, a new technique for the optimization of (partially) bound queries over disjunctive Datalog programs with stratified negation is presented. The technique exploits the propagation of query bindings and extends the Magic Set optimization technique (originally defined for non-disjunctive programs). An important feature of disjunctive Datalog programs is non-monotonicity, which calls for non-deterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the non-deterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined Magic Set methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically. The correctness of the method is established and proved in a formal way thanks to a strong relationship between Magic Sets and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method and the correctness proof also to programs with stratified negation in a natural way. The proposed method has been implemented in the DLV system and various experiments on synthetic as well as on real-world data have been conducted. The experimental results on synthetic data confirm the utility of Magic Sets for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method with respect to the previously proposed Magic Set method for disjunctive Datalog programs. Further experiments on data taken from a real-life application show the benefits of the Magic Set method within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information. [Copyright &y& Elsevier]

Query answering from inconsistent databases amounts to finding "meaningful" answers to queries posed over database instances that do not satisfy integrity constraints specified over their schema. A declarative approach to this problem relies on the notion of repair, that is, a database that satisfies integrity constraints and is obtained from the original inconsistent database by "minimally" adding and/or deleting tuples. Consistent answers to a user query are those answers that are in the evaluation of the query over each repair. Motivated by the fact that computing consistent answers from inconsistent databases is in general intractable, the present paper investigates techniques that allow to localize the difficult part of the computation on a small fragment of the database at hand, called "affected" part. Based on a number of localization results, an approach to query answering from inconsistent data is presented, in which the query is evaluated over each of the repairs of the affected part only, augmented with the part that is not affected. Single query results are then suitably recombined. For some relevant settings, techniques are also discussed to factorize repairs into components that can be processed independently of one another, thereby guaranteeing exponential gain w.r.t. the basic approach, which is not based on localization. The effectiveness of the results is demonstrated for consistent query answering over expressive schemas, based on logic programming specifications as proposed in the literature. [ABSTRACT FROM AUTHOR]

We study opinion diffusion on social graphs where agents hold binary opinions and where social pressure leads them to conform to the opinion manifested by the majority of their neighbors. We provide bounds relating the number of agents that suffice to spread an opinion to all other agents with the number of required propagation steps. Bounds are established constructively, via polynomial time algorithms that identify the agents that must act as seeds. In particular, we show that, on any given social graph G = (N , E) , it is possible to efficiently identify a set formed by half of the agents that can lead to consensus in min ⁡ { ⌊ | N | / 2 ⌋ , even (G) + 1 } propagation steps, where even (G) is the number of agents with an even number of neighbors in G. The result marks the boundary of tractability, since we show that the existence of sets of seeds consisting of less than half of the agents depends on certain features of the underlying graphs, which are NP-hard to identify. In fact, other NP-hardness results emerge from our analysis. In particular, by closing a problem left open in the literature, we show that it is intractable to decide whether further stable configurations exist in addition to the "consensus" ones (where all agents hold the same opinion). Eventually, for all these problems related to reasoning about opinion diffusion, we show that islands of tractability can be identified by focusing on classes of tree-like social graphs. [ABSTRACT FROM AUTHOR]

AI techniques and systems are pervasive to the media and entertainment industry, with application ranging from chatbots and characters to games and virtual environments. A common feature characterising these applications is given by the intent to introduce a narrative element in the user experience, often conveyed through some type of performance. In this paper, we analyse the contribution of AI techniques in the design and realization of a dramatic performance, an interactive system participated by human performers and audiences through some type of enactment. Drawing on real applications developed for innovative performances, we propose an architectural model that forms the technical platform of the system, and discuss how it can be deployed using Artificial Intelligence techniques with reference to real, experimental applications created in the last two decades. [ABSTRACT FROM AUTHOR]

In Machine Learning scenarios, privacy is a crucial concern when models have to be trained with private data coming from users of a service, such as a recommender system, a location-based mobile service, a mobile phone text messaging service providing next word prediction, or a face image classification system. The main issue is that, often, data are collected, transferred, and processed by third parties. These transactions violate new regulations, such as GDPR. Furthermore, users usually are not willing to share private data such as their visited locations, the text messages they wrote, or the photo they took with a third party. On the other hand, users appreciate services that work based on their behaviors and preferences. In order to address these issues, Federated Learning (FL) has been recently proposed as a means to build ML models based on private datasets distributed over a large number of clients, while preventing data leakage. A federation of users is asked to train a same global model on their private data, while a central coordinating server receives locally computed updates by clients and aggregate them to obtain a better global model, without the need to use clients' actual data. In this work, we extend the FL approach by pushing forward the state-of-the-art approaches in the aggregation step of FL, which we deem crucial for building a high-quality global model. Specifically, we propose an approach that takes into account a suite of client-specific criteria that constitute the basis for assigning a score to each client based on a priority of criteria defined by the service provider. Extensive experiments on two publicly available datasets indicate the merits of the proposed approach compared to standard FL baseline. [ABSTRACT FROM AUTHOR]

Recurrent Neural Networks (RNNs) represent a natural paradigm for modeling sequential data like text written in natural language. In fact, RNNs and their variations have long been the architecture of choice in many applications, however in practice they require the use of labored architectures (such as gating mechanisms) and computationally heavy training processes. In this paper we address the question of whether it is possible to generate sentence embeddings via completely untrained recurrent dynamics, on top of which to apply a simple learning algorithm for text classification. This would allow to obtain extremely efficient models in terms of training time. Our work investigates the extent to which this approach can be used, by analyzing the results on different tasks. Finally, we show that, within certain limits, it is possible to build extremely efficient models for text classification that remain competitive in accuracy with reference models in the state-of-the-art. [ABSTRACT FROM AUTHOR]

In this work we present PRONOM , a theorem prover and countermodel generator for non-normal modal logics. PRONOM implements some labelled sequent calculi recently introduced for the basic system E and its extensions with axioms M, N, and C based on bi-neighbourhood semantics. PRONOM is inspired by the methodology of leanTAP and is implemented in Prolog. When a modal formula is valid, then PRONOM computes a proof (a closed tree) in the labelled calculi having a sequent with an empty left-hand side and containing only that formula on the right-hand side as a root, otherwise PRONOM is able to extract a model falsifying it from an open, saturated branch. The paper shows some experimental results, witnessing that the performances of PRONOM are promising. [ABSTRACT FROM AUTHOR]

In recent years, Deep Learning methods have become very popular in classification tasks for Natural Language Processing (NLP); this is mainly due to their ability to reach high performances by relying on very simple input representations, i.e., raw tokens. One of the drawbacks of deep architectures is the large amount of annotated data required for an effective training. Usually, in Machine Learning this problem is mitigated by the usage of semi-supervised methods or, more recently, by using Transfer Learning, in the context of deep architectures. One recent promising method to enable semi-supervised learning in deep architectures has been formalized within Semi-Supervised Generative Adversarial Networks (SS-GANs) in the context of Computer Vision. In this paper, we adopt the SS-GAN framework to enable semi-supervised learning in the context of NLP. We demonstrate how an SS-GAN can boost the performances of simple architectures when operating in expressive low-dimensional embeddings; these are derived by combining the unsupervised approximation of linguistic Reproducing Kernel Hilbert Spaces and the so-called Universal Sentence Encoders. We experimentally evaluate the proposed approach over a semantic classification task, i.e., Question Classification, by considering different sizes of training material and different numbers of target classes. By applying such adversarial schema to a simple Multi-Layer Perceptron, a classifier trained over a subset derived from 1% of the original training material achieves 92% of accuracy. Moreover, when considering a complex classification schema, e.g., involving 50 classes, the proposed method outperforms state-of-the-art alternatives such as BERT. [ABSTRACT FROM AUTHOR]