Search results for "database."
showing 10 items of 2119 documents
Graph connectivity and monadic NP
2002
Ehrenfeucht games are a useful tool in proving that certain properties of finite structures are not expressible by formulas of a certain type. In this paper a new method is introduced that allows the extension of a local winning strategy for Duplicator, one of the two players in Ehrenfeucht games, to a global winning strategy. As an application it is shown that graph connectivity cannot be expressed by existential second-order formulas, where the second-order quantification is restricted to unary relations (monadic NP), even, in the presence of a built-in linear order. As a second application it is stated, that, on the other hand, the presence of a linear order increases the power of monadi…
Span-Program-Based Quantum Algorithms for Graph Bipartiteness and Connectivity
2016
Span program is a linear-algebraic model of computation which can be used to design quantum algorithms. For any Boolean function there exists a span program that leads to a quantum algorithm with optimal quantum query complexity. In general, finding such span programs is not an easy task. In this work, given a query access to the adjacency matrix of a simple graph G with n vertices, we provide two new span-program-based quantum algorithms:an algorithm for testing if the graph is bipartite that uses $$On\sqrt{n}$$ quantum queries;an algorithm for testing if the graph is connected that uses $$On\sqrt{n}$$ quantum queries.
Degree of monotonicity in aggregation process
2010
In this paper we introduce a fuzzy order relation notion in the description of aggregation process. Namely, we use the fuzzy order relation to define the degree of monotonicity, which is equal to 1 for a monotone function with respect to a crisp order relation. In that case, integration of fuzzy order relation allows us to generalize the notion of monotonicity and we try to investigate the benefits of using fuzzy relations instead of a crisp relation. Further we illustrate this definition by examples and study the properties of aggregation functions which have a certain degree of monotonicity.
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
2005
A language L over an alphabet A is said to have a neutral letter if there is a letter [email protected]?A such that inserting or deleting e's from any word in A^* does not change its membership or non-membership in L. The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language L with a neutral letter is not definable in first-order logic with linear order, then it is not definable in first-order logic with any set N of numerical predicates. Named after the location of its first, flawed, proof this conjecture is called the Crane Beach …
Termination of a set of rules modulo a set of equations
2006
The problem of termination of a set R of rules modulo a set E of equations, called E-termination problem, arises when trying to complete the set of rules in order to get a Church-Rosser property for the rules modulo the equations. We first show here that termination of the rewriting relation and E-termination are the same whenever the used rewriting relation is E-commuting, a property inspired from Peterson and Stickel’s E-compatibility property. More precisely, their results can be obtained by requiring termination of the rewriting relation instead of E-termination if E-commutation is used instead of E-compatibility. When the rewriting relation is not E-commuting, we show how to reduce E-t…
Grover’s Algorithm with Errors
2013
Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size n in \(O(\sqrt{n})\) queries, while any classical algorithm needs O(n) queries [3].
On the use of relational expressions in the design of efficient algorithms
2005
Relational expressions have finite binary relations as arguments and the operations are composition (·), closure (*), inverse (−1), and union (U). The efficient computation of the relation denoted by a relational expression is considered, and a tight bound is established on the complexity of the algorithm suggested by Hunt, Szymanski and Ullman. The result implies a unified method for deriving efficient algorithms for many problems in parsing. For example, optimal algorithms are derived for strong LL(1) and strong LL(2) parser construction and an efficient polynomialtime algorithm is derived for determining the inessential error entries in an LR(1) parsing table.
Understanding Quantum Algorithms via Query Complexity
2017
Query complexity is a model of computation in which we have to compute a function $f(x_1, \ldots, x_N)$ of variables $x_i$ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we su…
Locality of order-invariant first-order formulas
2000
A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.
Embedding finite linear spaces in projective planes, II
1987
Abstract It is shown that a finite linear space with maximal point degree n + 1 can be embedded in a projective plane of order n, provided that the line sizes are big enough.