Search results for "complex"
showing 10 items of 5889 documents
Positive Versions of Polynomial Time
1998
Abstract We show that restricting a number of characterizations of the complexity class P to be positive (in natural ways) results in the same class of (monotone) problems, which we denote by posP . By a well-known result of Razborov, posP is a proper subclass of the class of monotone problems in P . We exhibit complete problems for posP via weak logical reductions, as we do for other logically defined classes of problems. Our work is a continuation of research undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequently solve a problem posed by Grigni and Sipser.
Noise-tolerant efficient inductive synthesis of regular expressions from good examples
1997
We present an almost linear time method of inductive synthesis restoring simple regular expressions from one representative (good) example. In particular, we consider synthesis of expressions of star-height one, where we allow one union operation under each iteration, and synthesis of expressions without union operations from examples that may contain mistakes. In both cases we provide sufficient conditions defining precisely the class of target expressions and the notion of good examples under which the synthesis algorithm works correctly, and present the proof of correctness. In the case of expressions with unions the proof is based on novel results in the combinatorics of words. A genera…
Integrability of the one dimensional Schrödinger equation
2018
We present a definition of integrability for the one dimensional Schroedinger equation, which encompasses all known integrable systems, i.e. systems for which the spectrum can be explicitly computed. For this, we introduce the class of rigid functions, built as Liouvillian functions, but containing all solutions of rigid differential operators in the sense of Katz, and a notion of natural boundary conditions. We then make a complete classification of rational integrable potentials. Many new integrable cases are found, some of them physically interesting.
The arithmetic decomposition of central Cantor sets
2018
Abstract Every central Cantor set of positive Lebesgue measure is the arithmetic sum of two central Cantor sets of Lebesgue measure zero. Under some mild condition this result can be strengthened by stating that the summands can be chosen to be C s regular if the initial set is of this class.
Solutions of nonlinear PDEs in the sense of averages
2012
Abstract We characterize p-harmonic functions including p = 1 and p = ∞ by using mean value properties extending classical results of Privaloff from the linear case p = 2 to all pʼs. We describe a class of random tug-of-war games whose value functions approach p-harmonic functions as the step goes to zero for the full range 1 p ∞ .
FROM DISCRETE KINETIC AND STOCHASTIC GAME THEORY TO MODELLING COMPLEX SYSTEMS IN APPLIED SCIENCES
2004
This paper deals with some methodological aspects related to the discretization of a class of integro-differential equations modelling the evolution of the probability distribution over the microscopic state of a large system of interacting individuals. The microscopic state includes both mechanical and socio-biological variables. The discretization of the microscopic state generates a class of dynamical systems defining the evolution of the densities of the discretized state. In general, this yields a system of partial differential equations replacing the continuous integro-differential equation. As an example, a specific application is discussed, which refers to modelling in the field of…
Separation conditions on controlled Moran constructions
2017
It is well known that the open set condition and the positivity of the $t$-dimensional Hausdorff measure are equivalent on self-similar sets, where $t$ is the zero of the topological pressure. We prove an analogous result for a class of Moran constructions and we study different kinds of Moran constructions with this respect.
Positivity, complex FIOs, and Toeplitz operators
2018
International audience; We establish a characterization of complex linear canonical transformations that are positive with respect to a pair of strictly plurisubharmonic quadratic weights. As an application, we show that the boundedness of a class of Toeplitz operators on the Bargmann space is implied by the boundedness of their Weyl symbols.
The linearized Calderón problem on complex manifolds
2019
International audience; In this note we show that on any compact subdomain of a Kähler manifold that admits sufficiently many global holomorphic functions , the products of harmonic functions form a complete set. This gives a positive answer to the linearized anisotropic Calderón problem on a class of complex manifolds that includes compact subdomains of Stein manifolds and sufficiently small subdomains of Kähler manifolds. Some of these manifolds do not admit limiting Carleman weights, and thus cannot by treated by standard methods for the Calderón problem in higher dimensions. The argument is based on constructing Morse holo-morphic functions with approximately prescribed critical points.…
Efficient learning of regular expressions from good examples
1994
We consider the problem of restoring regular expressions from expressive examples. We define the class of unambiguous regular expressions, the notion of the union number of an expression showing how many union operations can occur directly under any single iteration, and the notion of an expressive example. We present a polynomial time algorithm which tries to restore an unambiguous regular expression from one expressive example. We prove that if the union number of the expression is 0 or 1 and the example is long enough, then the algorithm correctly restores the original expression from one good example. The proof relies on original investigations in theory of covering symbol sequences (wo…