Search results for "Computation"
showing 10 items of 7362 documents
Forests and pattern-avoiding permutations modulo pure descents
2018
Abstract We investigate an equivalence relation on permutations based on the pure descent statistic. Generating functions are given for the number of equivalence classes for the set of all permutations, and the sets of permutations avoiding exactly one pattern of length three. As a byproduct, we exhibit a permutation set in one-to-one correspondence with forests of ordered binary trees, which provides a new combinatorial class enumerated by the single-source directed animals on the square lattice. Furthermore, bivariate generating functions for these sets are given according to various statistics.
Extending the star order to Rickart rings
2015
Star partial order was initially introduced for semigroups and rings with (proper) involution. In particular, this order has recently been studied on Rickart *-rings. It is known that the star order in such rings can be characterized by conditions not involving involution explicitly. Owing to these characterizations, the order can be extended to certain special Rickart rings named strong in the paper; this extension is the objective of the paper. The corresponding order structure of strong Rickart rings is studied more thoroughly. In particular, the most significant lattice properties of star-ordered Rickart *-rings are successfully transferred to strong Rickart rings; also several new resu…
Miglioramento dell'approssimazione delle radici complesse, semplici e multiple di equazioni algebriche a coefficienti reali
1968
The paper shows an iterative procedure by which, starting from an approximate value of a root,z0=x0+jy0, of an algebraic equationF(z)=0, a sequence of values {zn} is obtained, aproximating the corresponding exact root; under certain conditions.
On complexity and motion planning for co-rank one sub-Riemannian metrics
2004
In this paper, we study the motion planning problem for generic sub-Riemannian metrics of co-rank one. We give explicit expressions for the metric complexity (in the sense of Jean (10,11)), in terms of the elementary invariants of the problem. We construct asymptotic optimal syntheses. It turns out that among the results we show, the most complicated case is the 3-dimensional. Besides the generic C ∞ case, we study some non-generic generalizations in the analytic case.
Nonlocal Quantum XOR Games for Large Number of Players
2010
Nonlocal games are used to display differences between classical and quantum world In this paper, we study nonlocal games with a large number of players We give simple methods for calculating the classical and the quantum values for symmetric XOR games with one-bit input per player, a subclass of nonlocal games We illustrate those methods on the example of the N-player game (due to Ardehali [Ard92]) that provides the maximum quantum-over-classical advantage.
Balance Properties and Distribution of Squares in Circular Words
2008
We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalised to non periodic infinite words as well.
Co-learnability and FIN-identifiability of enumerable classes of total recursive functions
1994
Co-learnability is an inference process where instead of producing the final result, the strategy produces all the natural numbers but one, and the omitted number is an encoding of the correct result. It has been proved in [1] that co-learnability of Goedel numbers is equivalent to EX-identifiability. We consider co-learnability of indices in recursively enumerable (r.e.) numberings. The power of co-learnability depends on the numberings used. Every r.e. class of total recursive functions is co-learnable in some r.e. numbering. FIN-identifiable classes are co-learnable in all r.e. numberings, and classes containing a function being accumulation point are not co-learnable in some r.e. number…
Exceptional Configurations of Quantum Walks with Grover’s Coin
2016
We study search by quantum walk on a two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. We show what the most natural coin transformation -- Grover's diffusion transformation -- has a wide class of exceptional configurations of marked locations, for which the probability of finding any of the marked locations does not grow over time. This extends the class of known exceptional configurations; until now the only known such configuration was the "diagonal construction" by [AR08].
Tighter Relations between Sensitivity and Other Complexity Measures
2014
The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].
Asymptotics for thenth-degree Laguerre polynomial evaluated atn
1992
We investigate the asymptotic behaviour of ? n (n),n?? where ? n (x) denotes the Laguerre polynomial of degreen. Our results give a partial answer to the conjecture ?? n (n)>1 forn>6, made in 1984 by van Iseghem. We also show the connection between this conjecture and the continued fraction approximants of $$6\sqrt {{3 \mathord{\left/ {\vphantom {3 \pi }} \right. \kern-\nulldelimiterspace} \pi }} $$ .