Search results for "Existential quantification"
showing 10 items of 39 documents
A motion planning algorithm for the invalid initial state disassembly problem
2015
Sampling-based motion planners are able to plan disassembly paths at high performance. They are limited by the fact that the input triangle sets of the static and dynamic object need to be free of collision in the initial and all following states. In real world applications, like the disassembly planning in car industry, this often does not hold true. Beside data inaccuracy, this is mainly caused by the modeling of flexible parts as rigid bodies, especially fixture elements like clips. They cause the invalid initial state disassembly problem. In the literature there exists no algorithm that is able to calculate a reasonable disassembly path for an invalid initial state. Our novel algorithm …
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.
On a Conjecture on Bidimensional Words
2003
We prove that, given a double sequence w over the alphabet A (i.e. a mapping from Z2 to A), if there exists a pair (n0, m0) ∈ Z2 such that pw(n0, m0) < 1/100n0m0, then w has a periodicity vector, where pw is the complexity function in rectangles of w.
Topological direct sum decompositions of banach spaces
1990
LetY andZ be two closed subspaces of a Banach spaceX such thatY≠lcub;0rcub; andY+Z=X. Then, ifZ is weakly countably determined, there exists a continuous projectionT inX such that ∥T∥=1,T(X)⊃Y, T −1(0)⊂Z and densT(X)=densY. It follows that every Banach spaceX is the topological direct sum of two subspacesX 1 andX 2 such thatX 1 is reflexive and densX 2**=densX**/X.
Universal Lyndon Words
2014
A word w over an alphabet Σ is a Lyndon word if there exists an order defined on Σ for which w is lexicographically smaller than all of its conjugates (other than itself). We introduce and study universal Lyndon words, which are words over an n-letter alphabet that have length n! and such that all the conjugates are Lyndon words. We show that universal Lyndon words exist for every n and exhibit combinatorial and structural properties of these words. We then define particular prefix codes, which we call Hamiltonian lex-codes, and show that every Hamiltonian lex-code is in bijection with the set of the shortest unrepeated prefixes of the conjugates of a universal Lyndon word. This allows us t…
A characterization of the n-ary many-sorted closure operators and a many-sorted Tarski irredundant basis theorem
2018
A theorem of single-sorted algebra states that, for a closure space (A, J ) and a natural number n, the closure operator J on the set A is n-ary if and only if there exists a single-sorted signature Σ and a Σ-algebra A such that every operation of A is of an arity ≤ n and J = SgA, where SgA is the subalgebra generating operator on A determined by A. On the other hand, a theorem of Tarski asserts that if J is an n-ary closure operator on a set A with n ≥ 2, then, for every i, j ∈ IrB(A, J ), where IrB(A, J ) is the set of all natural numbers which have the property of being the cardinality of an irredundant basis (≡ minimal generating set) of A with respect to J , if i < j and {i + 1, . . . …
Entropy-Based Behavioural Efficiency of the Financial Market
2021
The most known and used abstract model of the financial market is based on the concept of the informational efficiency (EMH) of that market. The paper proposes an alternative which could be named the behavioural efficiency of the financial market, which is based on the behavioural entropy instead of the informational entropy. More specifically, the paper supports the idea that, in the financial market, the only measure (if any) of the entropy is the available behaviours indicated by the implicit information. Therefore, the behavioural entropy is linked to the concept of behavioural efficiency. The paper argues that, in fact, in the financial markets, there is not a (real) informational effi…
Probabilistic and team PFIN-type learning: General properties
2008
We consider the probability hierarchy for Popperian FINite learning and study the general properties of this hierarchy. We prove that the probability hierarchy is decidable, i.e. there exists an algorithm that receives p_1 and p_2 and answers whether PFIN-type learning with the probability of success p_1 is equivalent to PFIN-type learning with the probability of success p_2. To prove our result, we analyze the topological structure of the probability hierarchy. We prove that it is well-ordered in descending ordering and order-equivalent to ordinal epsilon_0. This shows that the structure of the hierarchy is very complicated. Using similar methods, we also prove that, for PFIN-type learning…
On the Power of Non-adaptive Learning Graphs
2012
We introduce a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only require the knowledge of the disposition of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph, and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure and such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by cer…
Parity Oblivious d-Level Random Access Codes and Class of Noncontextuality Inequalities
2016
One of the fundamental results in quantum foundations is the Kochen-Specker no-go theorem. For the quantum theory, the no-go theorem excludes the possibility of a class of hidden variable models where value attribution is context independent. Recently, the notion of contextuality has been generalized for different operational procedures and it has been shown that preparation contextuality of mixed quantum states can be a useful resource in an information-processing task called parity-oblivious multiplexing. Here, we introduce a new class of information processing tasks, namely d-level parity oblivious random access codes and obtain bounds on the success probabilities of performing such task…