Search results for "combinatoric"

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].

Stochastic Processes on Ends of Tree and Dirichlet Forms

2016

We present main ideas and compare two constructions of stochastic processes on the ends (leaves) of the trees with varying numbers of edges at the nods. In one of them the trees are represented by spaces of numerical sequences and the processes are obtained by solving a class of Chapman-Kolmogorov Equations. In the other the trees are described by the set of nodes and edges. To each node there is naturally associated a finite dimensional function space and the Dirichlet form on it. Having a class of Dirichlet forms at the nodes one can under certain conditions build a Dirichlet form on L2 space of funcions on the ends of the trees. We show that the state spaces of two approaches are homeomo…

Two groups with isomorphic group algebras

1990

Extensions of Representable Positive Linear Functionals to Unitized Quasi *-Algebras: A New Method

2014

In this paper we introduce a topological approach for extending a representable linear functional \({\omega}\), defined on a topological quasi *-algebra without unit, to a representable linear functional defined on a quasi *-algebra with unit. In particular, we suppose that \({\omega}\) is continuous and the positive sesquilinear form \({\varphi_\omega}\), associated with \({\omega}\), is closable and prove that the extension \({\overline{\varphi_\omega}^e}\) of the closure \({\overline{\varphi_\omega}}\) is an i.p.s. form. By \({\overline{\varphi_\omega}^e}\) we construct the desired extension.

Partial spreads in finite projective spaces and partial designs

1975

A partial t-spread of a projective space P is a collection 5 p of t-dimensional subspaces of P of the same order with the property that any point of P is contained in at most one element of 50. A partial t-spread 5 p of P is said to be a t-spread if each point of P is contained in an element of 5P; a partial t-spread which is not a spread will be called strictly partial. Partial t-spreads are frequently used for constructions of affine planes, nets, and Sperner spaces (see for instance Bruck and Bose [5], Barlotti and Cofman [2]). The extension of nets to affine planes is related to the following problem: When can a partial t-spread 5 ~ of a projective space P be embedded into a larger part…

Bounded Bi-ideals and Linear Recurrence

2013

Bounded bi-ideals are a subclass of uniformly recurrent words. We introduce the notion of completely bounded bi-ideals by imposing a restriction on their generating base sequences. We prove that a bounded bi-ideal is linearly recurrent if and only if it is completely bounded.

"Indexing structures for approximate string matching

2003

In this paper we give the first, to our knowledge, structures and corresponding algorithms for approximate indexing, by considering the Hamming distance, having the following properties. i) Their size is linear times a polylog of the size of the text on average. ii) For each pattern x, the time spent by our algorithms for finding the list occ(x) of all occurrences of a pattern x in the text, up to a certain distance, is proportional on average to |x| + |occ(x)|, under an additional but realistic hypothesis.

On the spectrum of linear combinations of two projections inC*-algebras

2010

In this note, we study the spectrum and give estimations for the spectral radius of linear combinations of two projections in C*-algebras. We also study the commutator of two projections.

Comparing the relative volume with a revolution manifold as a model

1993

Given a pair (P, M), whereM is ann-dimensional connected compact Riemannian manifold andP is a connected compact hypersurface ofM, the relative volume of (P, M) is the quotient volume(P)/volume(M). In this paper we give a comparison theorem for the relative volume of such a pair, with some bounds on the Ricci curvature ofM and the mean curvature ofP, with respect to that of a model pair\(\left( {\mathcal{P},\mathcal{M}} \right)\) where ℳ is a revolution manifold and\(\mathcal{P}\) a “parallel” of ℳ.