Search results for "Computation theory"
showing 10 items of 336 documents
Time-Efficient Quantum Walks for 3-Distinctness
2013
We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.
The Phagocyte Lattice of Dyck Words
2006
We introduce a new lattice structure on Dyck words. We exhibit efficient algorithms to compute meets and joins of Dyck words.
Every triangle-free induced subgraph of the triangular lattice is(5m,2m)-choosable
2014
A graph G is (a,b)-choosable if for any color list of size a associated with each vertex, one can choose a subset of b colors such that adjacent vertices are colored with disjoint color sets. This paper proves that for any integer m>=1, every finite triangle-free induced subgraph of the triangular lattice is (5m,2m)-choosable.
A Motzkin filter in the Tamari lattice
2015
The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distan…
Matchings in three Catalan lattices
2003
In this note we consider a series of lattices that are enumerated by the well-known Catalan numbers. For each of these lattices, we exhibit a matching in a constructive way.
Dyck paths with a first return decomposition constrained by height
2018
International audience; We study the enumeration of Dyck paths having a first return decomposition with special properties based on a height constraint. We exhibit new restricted sets of Dyck paths counted by the Motzkin numbers, and we give a constructive bijection between these objects and Motzkin paths. As a byproduct, we provide a generating function for the number of Motzkin paths of height k with a flat (resp. with no flats) at the maximal height. (C) 2018 Elsevier B.V. All rights reserved.KeywordsKeyWords Plus:STATISTICS; STRINGS
Enumeration of Łukasiewicz paths modulo some patterns
2019
Abstract For any pattern α of length at most two, we enumerate equivalence classes of Łukasiewicz paths of length n ≥ 0 where two paths are equivalent whenever the occurrence positions of α are identical on these paths. As a byproduct, we give a constructive bijection between Motzkin paths and some equivalence classes of Łukasiewicz paths.
Language Recognition Power and Succinctness of Affine Automata
2016
In this work we study a non-linear generalization based on affine transformations of probabilistic and quantum automata proposed recently by Diaz-Caro and Yakaryilmaz [6] referred as affine automata. First, we present efficient simulations of probabilistic and quantum automata by means of affine automata which allows us to characterize the class of exclusive stochastic languages. Then, we initiate a study on the succintness of affine automata. In particular, we show that an infinite family of unary regular languages can be recognized by 2-state affine automata, whereas the number of states of any quantum and probabilistic automata cannot be bounded. Finally, we present the characterization …
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata
2007
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.
New Developments in Quantum Algorithms
2010
In this survey, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and OR gates of size N in time O(\sqrt{N}). This provides quantum speedups for any problem that can be expressed via Boolean formulas. This result can be also extended to span problems, a generalization of Boolean formulas. This provides an optimal quantum algorithm for any Boolean function in the black-box query model. The second new development is a quantum algorithm for solving systems of linear equations. In contrast with traditional algorithms that run in time O(N^{2.37...}) where N is the size of the system, the …