Search results for "combinatorics"
showing 10 items of 1770 documents
A rigidity theorem for the pair ${\cal q}{\Bbb C} P^n$ (complex hyperquadric, complex projective space)
1999
Given a compact Kahler manifold M of real dimension 2n, let P be either a compact complex hypersurface of M or a compact totally real submanifold of dimension n. Let \(\cal q\) (resp. \({\Bbb R} P^n\)) be the complex hyperquadric (resp. the totally geodesic real projective space) in the complex projective space \({\Bbb C} P^n\) of constant holomorphic sectional curvature 4\( \lambda \). We prove that if the Ricci and some (n-1)-Ricci curvatures of M (and, when P is complex, the mean absolute curvature of P) are bounded from below by some special constants and volume (P) / volume (M) \(\leq \) volume (\(\cal q\))/ volume \(({\Bbb C} P^n)\) (resp. \(\leq \) volume \(({\Bbb R} P^n)\) / volume …
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].
Ambainis-Freivalds’ Algorithm for Measure-Once Automata
2001
An algorithm given by Ambainis and Freivalds [1] constructs a quantum finite automaton (QFA) with O(log p) states recognizing the language Lp = {ai| i is divisible by p} with probability 1 - Ɛ , for any Ɛ > 0 and arbitrary prime p. In [4] we gave examples showing that the algorithm is applicable also to quantum automata of very limited size. However, the Ambainis-Freivalds algoritm is tailored to constructing a measure-many QFA (defined by Kondacs andWatrous [2]), which cannot be implemented on existing quantum computers. In this paper we modify the algorithm to construct a measure-once QFA of Moore and Crutchfield [3] and give examples of parameters for this automaton. We show for the lang…
Three-page encoding and complexity theory for spatial graphs
2004
We construct a series of finitely presented semigroups. The centers of these semigroups encode uniquely up to rigid ambient isotopy in 3-space all non-oriented spatial graphs. This encoding is obtained by using three-page embeddings of graphs into the product of the line with the cone on three points. By exploiting three-page embeddings we introduce the notion of the three-page complexity for spatial graphs. This complexity satisfies the properties of finiteness and additivity under natural operations.
On the empirical spectral distribution for certain models related to sample covariance matrices with different correlations
2021
Given [Formula: see text], we study two classes of large random matrices of the form [Formula: see text] where for every [Formula: see text], [Formula: see text] are iid copies of a random variable [Formula: see text], [Formula: see text], [Formula: see text] are two (not necessarily independent) sets of independent random vectors having different covariance matrices and generating well concentrated bilinear forms. We consider two main asymptotic regimes as [Formula: see text]: a standard one, where [Formula: see text], and a slightly modified one, where [Formula: see text] and [Formula: see text] while [Formula: see text] for some [Formula: see text]. Assuming that vectors [Formula: see t…
Two-view “cylindrical decomposition” of binary images
2001
This paper describes the discrete cylindrical algebraic decomposition (DCAD) construction along two orthogonal views of binary images. The combination of two information is used to avoid ambiguities for image recognition purposes. This algorithm associates an object connectivity graph to each connected component, allowing a complete description of the structuring information. Moreover, an easy and compact representation of the scene is achieved by using strings in a five letter alphabet. Examples on complex digital images are also provided. © 2001 Elsevier Science Inc.
Maslov Anomaly and the Morse Index Theorem
2001
Our starting point is again the phase space integral $$\displaystyle{ \text{e}^{\text{i}\hat{\varGamma }[\tilde{M}]} =\int \mathcal{D}\chi ^{a}\,\text{e}^{\text{i}S_{\text{fl}}[\chi,\tilde{M}]} }$$ (31.1) with periodic boundary conditions χ(0) = χ(T) and $$\displaystyle{ S_{\text{fl}}[\chi,\tilde{M}] = \frac{1} {2}\int _{0}^{T}dt\,\bar{\chi }_{ a}(t)\left [ \frac{\partial } {\partial t} -\tilde{M}(t)\right ]_{\phantom{a}b}^{a}\chi ^{b}(t)\;. }$$ (31.2) Here we have indicated that Sfl and \(\hat{\varGamma }\) depend on ηcl a and A i only through \(\tilde{M}_{\phantom{a}b}^{a}\): $$\displaystyle{ \tilde{M}(t)_{\phantom{a}b}^{a} =\omega ^{ac}\partial _{ c}\partial _{b}\mathcal{H}{\bigl (\eta _…
The Average State Complexity of the Star of a Finite Set of Words Is Linear
2008
We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.
Suffix Automata and Standard Sturmian Words
2007
Blumer et al. showed (cf. [3,2]) that the suffix automaton of a word w must have at least |w|+1 states and at most 2|w|-1 states. In this paper we characterize the language L of all binary words w whose minimal suffix automaton S(w) has exactly |w| + 1 states; they are precisely all prefixes of standard Sturmian words. In particular, we give an explicit construction of suffix automaton of words that are palindromic prefixes of standard words. Moreover, we establish a necessary and sufficient condition on S(w) which ensures that if w ∈ L and a ∈ {0, 1} then wa ∈ L. By using such a condition, we show how to construct the automaton S(wa) from S(w). More generally, we provide a simple construct…
The diamond partial order for strong Rickart rings
2016
The diamond partial order has been first introduced for matrices, and then discussed also in the general context of *-regular rings. We extend this notion to Rickart rings, and state various properties of the diamond order living on the so-called strong Rickart rings. In particular, it is compared with the weak space preorder and the star order; also existence of certain meets and joins under diamond order is discussed.