This study presents a Subject-Aware Transformer-based neural network designed for the Electroencephalogram (EEG) Emotion Recognition task (SATEER), which entails the analysis of EEG signals to classify and interpret human emotional states. SATEER processes the EEG waveforms by transforming them into Mel spectrograms, which can be seen as particular cases of images with the number of channels equal to the number of electrodes used during the recording process; this type of data can thus be processed using a Computer Vision pipeline. Distinct from preceding approaches, this model addresses the variability in individual responses to identical stimuli by incorporating a User Embedder module. This module enables the association of individual profiles with their EEGs, thereby enhancing classification accuracy. The efficacy of the model was rigorously evaluated using four publicly available datasets, demonstrating superior performance over existing methods in all conducted benchmarks. For instance, on the AMIGOS dataset (A dataset for Multimodal research of affect, personality traits, and mood on Individuals and GrOupS), SATEER's accuracy exceeds 99.8% accuracy across all labels and showcases an improvement of 0.47% over the state of the art. Furthermore, an exhaustive ablation study underscores the pivotal role of the User Embedder module and each other component of the presented model in achieving these advancements.

Fair allocation of indivisible goods presents intriguing challenges from both a social choice perspective and an algorithmic standpoint. Due to the indivisibility of goods, it is common for one agent to envy the bundle of goods assigned to another agent and, indeed, envy-free solutions do not exist in general. In line with the classical game-theoretic concept of Nucleolus in coalitional games, we propose that a fair allocation should minimize the agents’ dissatisfaction profile in a lexicographic manner, where the dissatisfaction of an agent is defined as her maximum envy towards other agents. Therefore, we seek allocations that minimize the maximum envy. In cases where multiple solutions have an equal maximum value, we minimize the second-worst value, and so on. Additionally, as is customary in fair division problems, we also consider an efficiency requirement: among the allocations with the best agents’ dissatisfaction profile, we prioritize those that maximize the sum of agents’ utilities, known as maximum social welfare. Such allocations, referred to as maxileximin allocations, always exist. In this study, we analyze the computational properties of maxileximin allocations in the context of fair allocation problems with constraints. Specifically, we focus on the Connected Fair Division problem, where goods correspond to the nodes of a graph, and a bundle of goods is allowed if the subgraph formed by those goods is connected. We demonstrate that the problem is F∆P2 -complete, even for instances with simple graphical structures such as path and star graphs. However, we identify islands of tractability for instances with more intricate graphs, such as those having bounded treewidth, provided that the number of agents is bounded by a fixed number and utility functions use small values.

Maximin share is a compelling notion of fairness proposed by Buddish as a relaxation of more traditional concepts for fair allocations of indivisible goods. In this paper we consider this notion within a setting where bundles of goods must induce connected subsets over an underlying graph. This setting received much attention in earlier literature, and our study answers a number of questions that were left open. First, we show that computing maximin share allocations is FΔ2P-complete, even when focusing on consistent scenarios, that is, where such allocations are a-priori guaranteed to exist. Moreover, the problem remains intractable if all agents have the same type, i.e., have the same utility functions, and if either the values returned by the utility functions are polynomially bounded, or the underlying graphs have a low degree of cyclicity (more precisely, have bounded treewidth). However, if these conditions hold all together, then computing maximin share allocations (or checking that none exists) becomes tractable. The result is established via machineries based on logspace alternating machines that use partial representations of connected bundles, which are interesting in their own.

In allocation problems with indivisible goods, money compensation is used to distribute worth in a fair way. Coalitional games provide a formal mathematical framework to model such problems, and the Shapley value is a solution concept widely used to realise a fair distribution. To overcome its intractability, we describe how to simplify allocation problems and we propose algorithms for computing lower bounds and upper bounds of the Shapley value that can be combined with approximation algorithms. The proposed techniques have been implemented and tested on a real-world application of allocation problems, namely, the Italian research assessment program known as VQR.

Matching games form a class of coalitional games that attracted much attention in the literature. Indeed, several results are known about the complexity of computing over them {solution concepts}. In particular, it is known that computing the Shapley value is intractable in general, formally #P-hard, and feasible in polynomial time over games defined on trees. In fact, it was an open problem whether or not this tractability result holds over classes of graphs properly including acyclic ones. The main contribution of the paper is to provide a positive answer to this question, by showing that the Shapley value is tractable for matching games defined over graphs having bounded treewidth. The proposed technique has been implemented and tested on classes of graphs having different sizes and treewidth at most three.

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 efforts 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.

In the database context, the hypertree decomposition method is used for query optimization, whereby conjunctive queries having a low degree of cyclicity can be recognized and decomposed automatically, and efficiently evaluated. Hypertree decompositions were introduced at ACM PODS 1999. The present paper reviews' in form of questions and answers' the main relevant concepts and algorithms and surveys selected related work including applications and test results.

Counting the number of answers to conjunctive queries is an intractable problem, formally #P-hard, even over classes of acyclic queries. However, Durand and Mengel have recently introduced the notion of quantified star size that, combined with hypertree decompositions, identifies islands of tractability for the problem. They also wonder whether such a notion precisely characterizes those classes for which the counting problem is tractable. We show that this is the case only for bounded-arity simple queries, where relation symbols cannot be shared by different query atoms. Indeed, we give a negative answer to the question in the general case, by exhibiting a more powerful structural method based on the novel concept of #-generalized hypertree decomposition. On classes of queries with bounded #-generalized hypertree width, counting answers is shown to be feasible in polynomial time, after a fixed-parameter polynomial-time preprocessing that only depends on the query structure. A weaker variant (but still more general than the technique based on the quantified starsize) is also proposed, for which tractability is established without any exponential dependency on the query size. Based on #-generalized hypertree decompositions, a hybrid decomposition method is eventually conceived, where structural properties of the query are exploited in combination with properties of the given database, such as keys or other (weaker) dependencies among attributes that limit the allowed combinations of values. Intuitively, such features may induce different structural properties that are not identified by the worst-possible database perspective of purely structural methods.

Mechanism design is considered in the context of fair allocations of indivisible goods with monetary compensation, by focusing on problems where agents' declarations on allocated goods can be verified before payments are performed. A setting is considered where verification might be subject to errors, so that payments have to be awarded under the presumption of innocence, as incorrect declared values do not necessarily mean manipulation attempts by the agents. Within this setting, a mechanism is designed that is shown to be truthful, efficient, and budget-balanced. Moreover, agents' utilities are fairly determined by the Shapley value of suitable coalitional games, and enjoy highly desirable properties such as equal treatment of equals, envy-freeness, and a stronger one called individual-optimality. In particular, the latter property guarantees that, for every agent, her/his utility is the maximum possible one over any alternative optimal allocation. The computational complexity of the proposed mechanism is also studied. It turns out that it is #P-complete so that, to deal with applications with many agents involved, two polynomial-time randomized variants are also proposed: one that is still truthful and efficient, and which is approximately budget-balanced with high probability, and another one that is truthful in expectation, while still budget-balanced and efficient.

In this work a new protocol for Voice over IP (VoIP) transmissions in wireless ad-hoc networks is proposed. Distributed architecture is necessary when dealing with dynamic environments, such as ports or battlefields, where creating infrastructures becomes expensive or impossible. Mobile ad-hoc networks (MANETs) are based on a peer-to-peer approach and each node participates in the organization of the whole network. VoIP over MANETs is a challenging issue due to the intrinsic distributed nature of the existing peer-to-peer paradigm. This paper proposes a new protocol, capable of ensuring a quality of service (QoS) level for VoIP calls over a MANET and to manage a large number of calls in the system. Novel metric and utility functions are proposed to perform the best path selection from source to destination nodes, respecting the QoS parameters for VoIP quality. In particular, an objective metric such as R-factor is considered, and a flexibility index is defined in order to maximize the number of acceptable VoIP calls. Performance evaluation shows that the proposed approach led to better network management in terms of admitted calls and respected QoS constraints.

Structural decomposition methods are query optimization methods specifically conceived in the database theory community to efficiently answer (near-)acyclic queries. We propose to demonstrate H-DB, an SQL query optimizer that combines classical quantitative optimization techniques with such structural decomposition methods, which so far have been just analyzed from the theoretical viewpoint. The system provides support to optimizing SQL queries with arbitrary output variables, aggregate operators, ORDER BY statements, and nested queries. H-DB can be put on top of any existing database management system supporting JDBC technology, by transparently interacting/replacing its standard query optimization module. However, to push at maximum its optimization capabilities, H-DB should be coupled with an ad-hoc physical semi-join operator, which (as a relevant example) we implemented and integrated within the PostgreSQL database management system.

The computational complexity of relevant corerelated questions for coalitional games is addressed from the coalition structure viewpoint, i.e., without assuming that the grand-coalition necessarily forms.In the analysis, games are assumed to be in "compact" form, i.e., their worth functions are implicitly given as polynomial-time computable functions over succinct game encodings provided as input.Within this setting, a complete picture of the complexity issues arising with the core, as well as with the related stability concepts of least core and cost of stability, is depicted.In particular, the special cases of superadditive games and of games whose sets of feasible coalitions are restricted over tree-like interaction graphs are also studied.

A promising paradigm, that answers crucial needs raised by emerging wireless applications, foresees the cooperation of multiple terminals over short-range wireless links while downloading multimedia contents over long-range cellular connections. Energy consumption reduction is just one of the potential benefits the cited communication paradigm might offer. Undoubtedly, the main issue raised by the new paradigm is to develop a model of cooperative behavior, which can best meet the expectations of all the cooperating entities. Unfortunately, classic minimization problem solutions are usually conflicting with the concept of fairness, as it is sensed by rational players. A joint use of classical optimization and game theory based approaches may contribute to overcome the highlighted dichotomy between user satisfaction and stable minimal energy cost allocations. This paper studies the interactions among users in the presence of a cooperative file-sharing service and seeks appropriate solutions to achieve the lowest energy consumption is possible while motivating users to cooperate.

Enforcing local consistency is a well-known technique to simplify the evaluation of conjunctive queries. It consists of repeatedly taking the semijion between every pair of (relations associated with) query atoms, until the procedure stabilizes. If some relation becomes empty, then the query has an empty answer. Otherwise, we cannot say anything in general, unless we have some information on the structure of the given query. In fact, a fundamental result in database theory states that the class of queries for which---on every database---local consistency entails global consistency is precisely the class of acyclic queries. In the last few years, several efforts have been made to define structural decomposition methods isolating larger classes of nearly-acyclic queries, yet retaining the same nice properties as acyclic ones. In particular, it is known that queries having bounded (generalized) hypertree-width can be evaluated in polynomial time, and that this structural property is also sufficient to guarantee that local consistency solves the problem, as for acyclic queries. However, the precise power of such an approach was an open problem: Is it the case that bounded generalized hypertree-width is also a necessary condition to guarantee that local consistency entails global consistency?

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

The database community has investigated many structure-driven methods, which guarantee that large classes of queries may be answered in (input-output) polynomial-time. However, despite their very nice computational properties, these methods are not currently used for practical applications, since they do not care about output variables and aggregate operators, and do not exploit quantitative information on the data. In fact, none of these methods has been implemented inside any available DBMS. This paper aims at filling this gap between theory and practice. First, we define an extension of the notion of hypertree decomposition, which is currently the most powerful structural method. This new version, called query-oriented hypertree decomposition, is a suitable relaxation of hypertree decomposition designed for query optimization, and such that output variables and aggregate operators can be dealt with. Based on this notion, a hybrid optimizer is implemented, which can be used on top of available DBMSs to compute query plans. The prototype is also integrated into the well-known open-source DBMS PostgreSQL. Finally, we validate our proposal with a thorough experimental activity, conducted on PostgreSQL and on a commercial DBMS, which shows that both systems may significantly benefit from using hypertree decompositions for query optimization.

Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning, which is very expressive in a precise mathematical sense: it allows one to express every property of finite structures that is decidable in the complexity class Σ P 2 (NP NP ). Thus, under widely believed assumptions, DLP is strictly more expressive than normal ( disjunction-free ) logic programming, whose expressiveness is limited to properties decidable in NP. Importantly, apart from enlarging the class of applications which can be encoded in the language, disjunction often allows for representing problems of lower complexity in a simpler and more natural fashion.This article presents the DLV system, which is widely considered the state-of-the-art implementation of disjunctive logic programming, and addresses several aspects. As for problem solving, we provide a formal definition of its kernel language, function-free disjunctive logic programs (also known as disjunctive datalog ), extended by weak constraints, which are a powerful tool to express optimization problems. We then illustrate the usage of DLV as a tool for knowledge representation and reasoning, describing a new declarative programming methodology which allows one to encode complex problems (up to Δ P 3 -complete problems) in a declarative fashion. On the foundational side, we provide a detailed analysis of the computational complexity of the language of DLV, and by deriving new complexity results we chart a complete picture of the complexity of this language and important fragments thereof.Furthermore, we illustrate the general architecture of the DLV system, which has been influenced by these results. As for applications, we overview application front-ends which have been developed on top of DLV to solve specific knowledge representation tasks, and we briefly describe the main international projects investigating the potential of the system for industrial exploitation. Finally, we report about thorough experimentation and benchmarking, which has been carried out to assess the efficiency of the system. The experimental results confirm the solidity of DLV and highlight its potential for emerging application areas like knowledge management and information integration.

Peer-to-Peer (P2P) data integration systems have recently attracted significant attention for their ability to manage and share data dispersed over different peer sources. While integrating data for answering user queries, it often happens that inconsistencies arise, because some integrity constraints specified on peers' global schemas may be violated. In these cases, we may give semantics to the inconsistent system by suitably "repairing" the retrieved data, as typically done in the context of traditional data integration systems. However, some specific features of P2P systems, such as peer autonomy and peer preferences (e.g., different source trusting), should be properly addressed to make the whole approach effective. In this paper, we face these issues that were only marginally considered in the literature. We first present a formal framework for reasoning about autonomous peers that exploit individual preference criteria in repairing the data. The idea is that queries should be answered over the best possible database repairs with respect to the preferences of all peers, i.e., the states on which they are able to find an agreement. Then, we investigate the computational complexity of dealing with peer agreements and of answering queries in P2P data integration systems. It turns out that considering peer preferences makes these problems only mildly harder than in traditional data integration systems.

We investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash Equilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium is SigmaP2-complete. We then study practically relevant restrictions that lower the complexity. In particular, we are interested in quantitative and qualitative restrictions of the way each player's payoff depends on moves of other players. We say that a game has small neighborhood if the utility function for each player depends only on (the actions of) a logarithmically small number of other players. The dependency structure of a game G can be expressed by a graph DG(G) or by a hypergraph H(G). By relating Nash equilibrium problems to constraint satisfaction problems (CSPs), we show that if G has small neighborhood and if H(G) has bounded hypertree width (or if DG(G) has bounded treewidth), then finding pure Nash and Pareto equilibria is feasible in polynomial time. If the game is graphical, then these problems are LOGCFL-complete and thus in the class NC2 of highly parallelizable problems.

Abduction, first proposed in the setting of classical logics, has been studied with growing interest in the logic programming area during the last years. In this paper we study abduction with penalization in the logic programming framework. This form of abductive reasoning, which has not been previously analyzed in logic programming, turns out to represent several relevant problems, including optimization problems, very naturally. We define a formal model for abduction with penalization over logic programs, which extends the abductive framework proposed by Kakas and Mancarella. We address knowledge representation issues, encoding a number of problems in our abductive framework. In particular, we consider some relevant problems, taken from different domains, ranging from optimization theory to diagnosis and planning; their encodings turn out to be simple and elegant in our formalism. We thoroughly analyze the computational complexity of the main problems arising in the context of abduction with penalization from logic programs. Finally, we implement a system supporting the proposed abductive framework on top of the DLV engine. To this end, we design a translation from abduction problems with penalties into logic programs with weak constraints. We prove that this approach is sound and complete.

Hypertree width [22, 25] 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 about structural properties.In this paper, we define the notion of weighted hypertree decomposition, in order to combine structural decomposition methods with quantitative approaches. Weighted hypertree decompositions are equipped with cost functions, that can be used for modelling many situations where we have further information on the given problem, besides its hypergraph representation. We analyze the complexity of computing the hypertree decompositions having the smallest weights, called minimal hypertree decompositions. We show that, in many cases, adding weights we loose tractability. However, we prove 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, we provide a cost function that models query evaluation costs and show how to exploit weighted hypertree decompositions for determining (logical) query plans for answering conjunctive queries. Finally, we present the results of an experimental comparison of this query optimization technique with the query optimization of a commercial DBMS. These preliminary results are very promising, as for some large queries (with many joins) our hybrid technique clearly outperforms the commercial optimizer.

This paper presents a rule-based declarative database language which extends DATALOG to express events and nondeterministic state transitions, by using the choice construct to model uncertainty in dynamic rules. The proposed language, called Event Choice DATALOG (DATALOG!ev for short), provides a powerful mechanism to formulate queries on the evolution of a knowledge base, given a sequence of events envisioned to occur in the future. A distinguished feature of this language is the use of multiple spatio-temporal dimensions in order to model a finer control of evolution. A comprehensive study of the computational complexity of answering DATALOG!ev queries is reported.

Almost all semantics for logic programs with negation identify a set, SEM(P), of models of program P, as the intended semantics of P, and any model M in this class is considered a possible meaning of P with regard to the semantics the user has in mind. Thus, for example, in the case of stable models [M. Gelfond et al., (1988)], choice models [D. Sacca et al., (1990)], answer sets [M. Gelfond et al., (1991)], etc., different possible models correspond to different ways of "completing" the incomplete information in the logic program. However, different end-users may have different ideas on which of these different models in SEM(P) is a reasonable one from their point of view. For instance, given SEM(P), user U/sub 1/ may prefer model M/sub 1//spl isin/SEM(P) to model M/sub 2//spl isin/SEM(P) based on some evaluation criterion that she has. We develop a logic program semantics based on optimal models. This semantics does not add yet another semantics to the logic programming arena - it takes as input an existing semantics SEM(P) and a user-specified objective function Obj, and yields a new semantics Opt(P)_/spl sube/ SEM(P) that realizes the objective function within the framework of preferred models identified already by SEM(P). Thus, the user who may or may not know anything about logic programming has considerable flexibility in making the system reflect her own objectives by building "on top" of existing semantics known to the system. In addition to the declarative semantics, we provide a complete complexity analysis and algorithms to compute optimal models under varied conditions when SEM(P) is the stable model semantics, the minimal models semantics, and the all-models semantics.

In this paper we investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash Equilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium is ΣP2-complete. We then study practically relevant restrictions that lower the complexity. In particular, we are interested in quantitative and qualitative restrictions of the way each player's move depends on moves of other players. We say that a game has small neighborhood if the utility function for each player depends only on (the actions of) a logarithmically small number of other players, The dependency structure of a game 𝒢 can he expressed by a graph G(𝒢) or by a hypergraph H(𝒢). Among other results, we show that if 𝒢 has small neighborhood and if H(𝒢) has bounded hypertree width (or if G(𝒢) has bounded treewidth), then finding pure Nash and Pareto equilibria is feasible in polynomial time. If the game is graphical, then these problems are LOGCFL-complete and thus in the class NC2 of highly parallelizable problems.

In a previous paper [10], the authors introduced the notion of hypertree decomposition and the corresponding concept of hypertree width and showed that the conjunctive queries whose hypergraphs have bounded hypertree-width can be evaluated in polynomial time. Bounded hypertree-width generalizes the notions of acyclicity and bounded treewidth and corresponds to larger classes of tractable queries. In the present paper, we provide natural characterizations of hypergraphs and queries having bounded hypertree-width in terms of game-theory and logic.

This paper deals with the evaluation of acyclic Boolean conjunctive queries in relational databases. By well-known results of Yannakakis[1981], this problem is solvable in polynomial time; its precise complexity, however, has not been pinpointed so far. We show that the problem of evaluating acyclic Boolean conjunctive queries is complete for LOGCFL, the class of decision problems that are logspace-reducible to a context-free language. Since LOGCFL is contained in AC1 and NC2, the evaluation problem of acyclic Boolean conjunctive queries is highly parallelizable. We present a parallel database algorithm solving this problem with alogarithmic number of parallel join operations. The algorithm is generalized to computing the output of relevant classes of non-Boolean queries. We also show that the acyclic versions of the following well-known database and AI problems are all LOGCFL-complete: The Query Output Tuple problem for conjunctive queries, Conjunctive Query Containment, Clause Subsumption, and Constraint Satisfaction. The LOGCFL-completeness result is extended to the class of queries of bounded tree width and to other relevant query classes which are more general than the acyclic queries.

Article Hypertree decompositions and tractable queries Share on Authors: Georg Gottlob Inst. für Informationssysteme, Technische Universität Wien, A-1040 Vienna, Austria Inst. für Informationssysteme, Technische Universität Wien, A-1040 Vienna, AustriaView Profile , Nicola Leone Inst. für Informationssysteme, Technische Universität Wien, A-1040 Vienna, Austria Inst. für Informationssysteme, Technische Universität Wien, A-1040 Vienna, AustriaView Profile , Francesco Scarcello ISI-CNR, Via P. Bucci 41/C, I-87030 Rende, Italy ISI-CNR, Via P. Bucci 41/C, I-87030 Rende, ItalyView Profile Authors Info & Claims PODS '99: Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsMay 1999 Pages 21–32https://doi.org/10.1145/303976.303979Online:01 May 1999Publication History 52citation1,051DownloadsMetricsTotal Citations52Total Downloads1,051Last 12 Months9Last 6 weeks1 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 show that the problem of evaluating acylic Boolean database-queries is LOGCFL-complete and thus highly parallelizable. We present a parallel database algorithm solving this problem with a logarithmic number of parallel join operations. It follows from our main result that the acylic versions of the following important database and Al problems are LOGCFL-complete: The query output tuple problem for conjunctive queries, conjunctive query containment, clause subsumption, and constraint satisfaction.