Search results for " function"
showing 10 items of 9395 documents
Certain subclasses of multivalent analytic functions defined by multiplier transforms
2010
By making use of the principle of subordination between analytic functions and a family of multiplier transforms, we introduce and investigate some new subclasses of multivalent analytic functions. Such results as inclusion relationships, subordination and superordination properties, integral-preserving properties, argument estimates and convolution properties are proved.
An extension of the Burrows-Wheeler Transform and applications to sequence comparison and data compression
2005
We introduce a generalization of the Burrows-Wheeler Transform (BWT) that can be applied to a multiset of words. The extended transformation, denoted by E, is reversible, but, differently from BWT, it is also surjective. The E transformation allows to give a definition of distance between two sequences, that we apply here to the problem of the whole mitochondrial genome phylogeny. Moreover we give some consideration about compressing a set of words by using the E transformation as preprocessing.
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines
1999
The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this class if and only if there is a formula of the form ∃f1..∃fk∃R1..∃Rm∀xφv; that is true exactly for all strings in L. In this formula the fi are unary function symbols, the Ri are unary relation symbols and φv; is a quantifierfree formula. Furthermore, the quantification of functions is restricted to non-crossing, decreasing functions and in φv; no equations in which different functions occur are allowed. There are a number of variations of this statement, e.g., it holds also for k = 3. From these r…
2-SYMMETRIC CRITICAL POINT THEOREMS FOR NON-DIFFERENTIABLE FUNCTIONS
2008
AbstractIn this paper, some min–max theorems for even andC1functionals established by Ghoussoub are extended to the case of functionals that are the sum of a locally Lipschitz continuous, even term and a convex, proper, lower semi-continuous, even function. A class of non-smooth functionals admitting an unbounded sequence of critical values is also pointed out.
TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
2013
We examine the minimum amount of memory for real-time, as opposed to one-way, computation accepting nonregular languages. We consider deterministic, nondeterministic and alternating machines working within strong, middle and weak space, and processing general or unary inputs. In most cases, we are able to show that the lower bounds for one-way machines remain tight in the real-time case. Memory lower bounds for nonregular acceptance on other devices are also addressed. It is shown that increasing the number of stacks of real-time pushdown automata can result in exponential improvement in the total amount of space usage for nonregular language recognition.
Rademacher Theorem for Fréchet spaces
2010
Abstract Let X be a separable Frechet space. In this paper we define a class A of null sets in X that is properly contained in the class of Aronszajn null sets, and we prove that a Lipschitz map from an open subset of X into a Gelfand-Frechet space is Gateaux differentiable outside a set belonging to A. This is an extension to Frechet spaces of a result (see [PZ]) due to D. Preiss and L. Zajicek.
On the Russo-Dye Theorem for positive linear maps
2019
Abstract We revisit a classical result, the Russo-Dye Theorem, stating that every positive linear map attains its norm at the identity.
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 …
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
2014
Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy [7], is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity and 0-sensitivity and 0-block sensitivity.
General inductive inference types based on linearly-ordered sets
1996
In this paper, we reconsider the definitions of procrastinating learning machines. In the original definition of Freivalds and Smith [FS93], constructive ordinals are used to bound mindchanges. We investigate the possibility of using arbitrary linearly ordered sets to bound mindchanges in a similar way. It turns out that using certain ordered sets it is possible to define inductive inference types more general than the previously known ones. We investigate properties of the new inductive inference types and compare them to other types.