Disjoint pattern matching and implication in strings

We deal with the problem of deciding whether a given set of string patterns implies the presence of a fixed pattern. While checking whether a set of patterns occurs in a string is solvable in polynomial time, this implication problem is well known to be intractable. Here we consider a version of the problem when patterns in the set are required to be disjoint. We show that for such a version of the problem the situation is reversed: checking whether a set of patterns occurs in a string is NP-complete, but the implication problem is solvable in polynomial time.     

The three-color and two-color Tantrix™ rotation puzzle problems are NP-complete via parsimonious reductions

Holzer and Holzer [M. Holzer, W. Holzer, Tantrix? rotation puzzles are intractable, Discrete Applied Mathematics 144(3) (2004) 345–358] proved that the Tantrix? rotation puzzle problem with four colors is NP-complete, and they showed that the infinite variant of this problem is undecidable. In this paper, we study the three-color and two-color Tantrix? rotation puzzle problems (3-TRP and 2-TRP) and their variants. Restricting the number of allowed colors to three (respectively, to two) reduces the set of available Tantrix? tiles from 56 to 14 (respectively, to 8). We prove that 3-TRP and 2-TRP are NP-complete, which answers a question raised by Holzer and Holzer [M. Holzer, W. Holzer, Tantrix? rotation puzzles are intractable, Discrete Applied Mathematics 144(3) (2004) 345–358] in the affirmative. Since our reductions are parsimonious, it follows that the problems Unique-3-TRP and Unique-2-TRP are DP-complete under randomized reductions. We also show that the another-solution problems associated with 4-TRP, 3-TRP, and 2-TRP are NP-complete. Finally, we prove that the infinite variants of 3-TRP and 2-TRP are undecidable.     

Foundations of secure deductive databases

We develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called “yes-no” dialogs, and “yes-no-don't know” dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time-hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don't know dialogs     

Towards Formal Verification of Role-Based Access Control Policies

Specifying and managing access control policies is a challenging problem. We propose to develop formal verification techniques for access control policies to improve the current state of the art of policy specification and management. In this paper, we formalize classes of security analysis problems in the context of Role-Based Access Control. We show that in general these problems are PSPACE-complete. We also study the factors that contribute to the computational complexity by considering a lattice of various subcases of the problem with different restrictions. We show that several subcases remain PSPACE-complete, several further restricted subcases are NP-complete, and identify two subcases that are solvable in polynomial time. We also discuss our experiences and findings from experimentations that use existing formal method tools, such as model checking and logic programming, for addressing these problems.     

Using sticker model of DNA computing to solve domatic partition, kernel and induced path problems

DNA computing as a powerful interdisciplinary field has been found to be very useful and applicable for solving NP-complete and intractable problems because of its huge power in parallel processing. In recent years many efforts have been done to solve NP-complete and time consuming problems with the help of DNA computing. In this paper, we use sticker model (one of the most well-known models of DNA computing) to present three DNA algorithms for solving three different NP-complete graph-based problems for the first time: domatic partition, kernel and induced path. Also we have simulated these algorithms to show their correctness.     

Temporal logic query checking: a tool for model exploration

Temporal logic query checking was first introduced by W. Chan in order to speed up design understanding by discovering properties not known a priori. A query is a temporal logic formula containing a special symbol ?/sub 1/, known as a placeholder. Given a Kripke structure and a propositional formula /spl phi/, we say that /spl phi/ satisfies the query if replacing the placeholder by /spl phi/ results in a temporal logic formula satisfied by the Kripke structure. A solution to a temporal logic query on a Kripke structure is the set of all propositional formulas that satisfy the query. Query checking helps discover temporal properties of a system and, as such, is a useful tool for model exploration. In this paper, we show that query checking is applicable to a variety of model exploration tasks, ranging from invariant computation to test case generation. We illustrate these using a Cruise Control System. Additionally, we show that query checking is an instance of a multi-valued model checking of Chechik et al. This approach enables us to build an implementation of a temporal logic query checker, TLQSolver, on top of our existing multi-valued model checker /sub /spl chi//Chek. It also allows us to decide a large class of queries and introduce witnesses for temporal logic queries-an essential notion for effective model exploration.     

Redundancy in logic II: 2CNF and Horn propositional formulae

We report results about the redundancy of formulae in 2CNF form. In particular, we give a slight improvement over the trivial redundancy algorithm and give some complexity results about some problems related to finding Irredundant Equivalent Subsets (i.e.s.) of 2CNF formulae. The problems of checking whether a 2CNF formula has a unique i.e.s. and checking whether a clause in is all its i.e.s.'s are polynomial. Checking whether a 2CNF formula has an i.e.s. of a given size and checking whether a clause is in some i.e.s.'s of a 2CNF formula are polynomial or NP-complete depending on whether the formula is cyclic. Some results about Horn formulae are also reported.     

On the consistency of cardinal direction constraints

We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a co-ordinate system. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We introduce the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm, we prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in O(n⁵) time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss an extension to the basic model and outline an algorithm for the consistency checking problem of this extension.     

Independence results about context-free languages and lower bounds

We show that for any axiomatizable, sound formal system F there exist instances of natural problems about context-free languages, lower bounds of computations and P versus NP that are not provable in F for any recursive representation of these problems. Most previous independence results in computer science have been proven for specific representations of the problems, by exploiting the ‘opaqueness’ of Turing machine names. Our results rely on the complexity of the logical structure of the problem and yield independence results which do not depend on the representations of problems. We show, for example, that there exists a nonregular context-free language L₀ such that for no cf-grammar G, L(G) = L₀, it is provable in F that “L(G) is not regular”. We also show, among other results about P and NP, that there exists a recursive oracle A such that NP^A ≠ P^A, and that this fact is not provable in F for any recursive representation of A.

The difference of what is and is not provable in F is well illustrated by questions about polynomial time isomorphisms (p-isomorphisms) of NP-complete sets. We show that for every NP-complete set, L, there is a representation of L by a nondeterministic polynomial time machine for which we can prove that L is NP-complete. Furthermore, if L is p-isomorphic to SAT, then this is also provable in F for some representation of L. On the other hand, if there exist NP-complete sets not p-isomorphic to SAT, then there exists an NP-complete set L for which, independent of its representation, there is no proof in F that L is or is not p-isomorphic to SAT.     

On the Complexity of Iterated Weak Dominance in Constant-Sum Games

In game theory, an action is said to be weakly dominated if there exists another action of the same player that, with respect to what the other players do, is never worse and sometimes strictly better. We investigate the computational complexity of the process of iteratively eliminating weakly dominated actions (IWD) in two-player constant-sum games, i.e., games in which the interests of both players are diametrically opposed. It turns out that deciding whether an action is eliminable via IWD is feasible in polynomial time whereas deciding whether a given subgame is reachable via IWD is NP-complete. The latter result is quite surprising, as we are not aware of other natural computational problems that are intractable in constant-sum normal-form games. Furthermore, we slightly improve on a result of V. Conitzer and T. Sandholm by showing that typical problems associated with IWD in win-lose games with at most one winner are NP-complete.     

Incremental sequence-based frequent query pattern mining from XML queries

Existing algorithms of mining frequent XML query patterns (XQPs) employ a candidate generate-and-test strategy. They involve expensive candidate enumeration and costly tree-containment checking. Further, most of existing methods compute the frequencies of candidate query patterns from scratch periodically by checking the entire transaction database, which consists of XQPs transferred from user query logs. However, it is not straightforward to maintain such discovered frequent patterns in real XML databases as there may be frequent updates that may not only invalidate some existing frequent query patterns but also generate some new frequent query patterns. Therefore, a drawback of existing methods is that they are rather inefficient for the evolution of transaction databases. To address above-mentioned problems, this paper proposes an efficient algorithm ESPRIT to mine frequent XQPs without costly tree-containment checking. ESPRIT transforms XML queries into sequences using a one-to-one mapping technique and mines the frequent sequences to generate frequent XQPs. We propose two efficient incremental algorithms, ESPRIT-i and ESPRIT-i ⁺, to incrementally mine frequent XQPs. We devise several novel optimization techniques of query rewriting, cache lookup, and cache replacement to improve the answerability and the hit rate of caching. We have implemented our algorithms and conducted a set of experimental studies on various datasets. The experimental results demonstrate that our algorithms achieve high efficiency and scalability and outperform state-of-the-art methods significantly.     

A family of NP-complete data aggregation problems

Summary We consider a family of general aggregation problems and prove each of its members to be NP-complete in the strong sense. These problems require that we partition a set of objects into aggregates. The goal is to minimize the expected cost of satisfying an anticipated collection of requests for subsets of the objects, where the cost of satisfying a request includes both the number and the sizes of the aggregates which must be retrieved. The aggregation problems are viewed as very basic versions of important database optimization problems, including: the partitioning of data items into record types, the clustering of records into physical blocks of storage, and the partitioning of a database into granules to support locking. The NP-completeness results demonstrate that such optimization problems are intractable, even when simplified to the extreme. The fact that the problems are NP-complete in the strong sense also rules out pseudopolynomial time solutions, unless P = NP.     

Parallel bioinspired algorithms for NP complete graph problems

It is no longer believed that DNA computing will outperform digital computers when it comes to the computation of intractable problems. In this paper, we emphasise the in silico implementation of DNA-inspired algorithms as the only way to compete with other algorithms for solving NP-complete problems. For this, we provide sticker algorithms for some of the most representative NP-complete graph problems. The simple data structures and bit-vertical operations make them suitable for some parallel architectures. The parallel algorithms might solve either moderate-size problems in an exact manner or, when combined with a heuristic, large problems in polynomial time.     

The dynamic predicate: integrating access control with query processing in XML databases

Recently, access control on XML data has become an important research topic. Previous research on access control mechanisms for XML data has focused on increasing the efficiency of access control itself, but has not addressed the issue of integrating access control with query processing. In this paper, we propose an efficient access control mechanism tightly integrated with query processing for XML databases. We present the novel concept of the dynamic predicate (DP), which represents a dynamically constructed condition during query execution. A DP is derived from instance-level authorizations and constrains accessibility of the elements. The DP allows us to effectively integrate authorization checking into the query plan so that unauthorized elements are excluded in the process of query execution. Experimental results show that the proposed access control mechanism improves query processing time significantly over the state-of-the-art access control mechanisms. We conclude that the DP is highly effective in efficiently checking instance-level authorizations in databases with hierarchical structures.     

Consistency checking reduced to satisfiability of concepts in terminological systems

We investigate the inference problem in knowledge representation systems of theKl-one family. These systems, also called terminological systems, are equipped with concept languages that are used to express the conceptual knowledge of a problem domain in a structured way. In order to reason with the represented knowledge, terminological systems provide a couple of inference services. In this paper we show that the main reasoning problems in expressive concept languages can be reduced to a particular inference problem, namely checking satisfiability of concepts. This result has two important applications. From a practical point of view, our reduction together with the existence of relatively efficient implementations of satisfiability algorithms strongly simplifies the implementation of inference algorithms in terminological systems. Even from a complexity point of view, the result shows that in the underlying concept language interesting inference problems such as consistency checking or query answering are not harder (in terms of the worst case complexity) than satisfiability checking of concepts.This work has been carried out while the author was an employee of the German Research Center for AI (DFKI GmbH), Saarbrücken, Germany.     

On point-duration networks for temporal reasoning

We present here a point-duration network formalism which extends the point algebra model to include additional variables that represent durations between points of time. Thereafter the new qualitative model is enlarged for allowing unary metric constraints on points and durations, subsuming in this way several point-based approaches to temporal reasoning. We deal with some reasoning tasks within the new models and we show that the main problem, deciding consistency, is NP-complete. However, tractable special cases are identified and we show efficient algorithms for checking consistency, finding a solution and obtaining the minimal network.     

semQA: SPARQL with Idempotent Disjunction

The SPARQL LeftJoin abstract operator is not distributive over Union; this limits the algebraic manipulation of graph patterns, which in turn restricts the ability to create query plans for distributed processing or query optimization. In this paper, we present semQA, an algebraic extension for the SPARQL query language for RDF, which overcomes this issue by transforming graph patterns through the use of an idempotent disjunction operator Or as a substitute for Union. This permits the application of a set of equivalences that transform a query into distinct forms. We further present an algorithm to derive the solution set of the original query from the solution set of a query where Union has been substituted by Or. We also analyze the combined complexity of SPARQL, proving it to be NP-complete. It is also shown that the SPARQL query language is not, in the general case, fixed-parameter tractable. Experimental results are presented to validate the query evaluation methodology presented in this paper against the SPARQL standard, to corroborate the complexity analysis, and to illustrate the gains in processing cost reduction that can be obtained through the application of semQA.     

On querying simple conceptual graphs with negation

We consider basic conceptual graphs, namely simple conceptual graphs (SGs), which are equivalent to the existential conjunctive positive fragment of first-order logic. The fundamental problem, deduction, is performed by a graph homomorphism called projection. The existence of a projection from a SG Q to a SG G means that the knowledge represented by Q is deducible from the knowledge represented by G. In this framework, a knowledge base is composed of SGs representing facts and a query is itself a SG. We focus on the issue of querying SGs, which highlights another fundamental problem, namely query answering. Each projection from a query to a fact defines an answer to the query, with an answer being itself a SG. The query answering problem asks for all answers to a query.

This paper introduces atomic negation into this framework. Several understandings of negation are explored, which are all of interest in real world applications. In particular, we focus on situations where, in the context of incomplete knowledge, classical negation is not satisfactory because deduction can be proven but there is no answer to the query. We show that intuitionistic deduction captures the notion of an answer and can be solved by projection checking. Algorithms are provided for all studied problems. They are all based on projection. They can thus be combined to deal with several kinds of negation simultaneously. Relationships with problems on conjunctive queries in databases are recalled and extended. Finally, we point out that this discussion can be put in the context of semantic web databases.     

The Tractability of Segmentation and Scene Analysis

One of the fundamental problems in computer vision is the segmentation of an image into semantically meaningful regions, based only on image characteristics. A single segmentation can be determined using a linear number of evaluations of a uniformity predicate. However, minimising the number of regions is shown to be an NP-complete problem. We also show that the variational approach to segmentation, based on minimising a criterion combining the overall variance of regions and the number of regions, also gives rise to an NP-complete problem.When a library of object models is available, segmenting the image becomes a problem of scene analysis. A sufficient condition for the reconstruction of a 3D scene from a 2D image to be solvable in polynomial time is that the scene contains no cycles of mutually occluding objects and that no range information can be deduced from the image. It is known that relaxing the no cycles condition renders the problem NP-complete. We show that relaxing the no range information condition also produces an NP-complete problem.     

Well-definedness and semantic type-checking for the nested relational calculus

The well-definedness problem for a programming language consists of checking, given an expression and an input type, whether the semantics of the expression is defined for all inputs adhering to the input type. A related problem is the semantic type-checking problem which consists of checking, given an expression, an input type, and an output type whether the expression always returns outputs adhering to the output type on inputs adhering to the input type. Both problems are undecidable for general-purpose programming languages. In this paper we study these problems for the Nested Relational Calculus, a specific-purpose database query language. We also investigate how these problems behave in the presence of programming language features such as singleton coercion and type tests.