Search results for "Computation"
showing 10 items of 7362 documents
Importance sampling for Lambda-coalescents in the infinitely many sites model
2011
We present and discuss new importance sampling schemes for the approximate computation of the sample probability of observed genetic types in the infinitely many sites model from population genetics. More specifically, we extend the 'classical framework', where genealogies are assumed to be governed by Kingman's coalescent, to the more general class of Lambda-coalescents and develop further Hobolth et. al.'s (2008) idea of deriving importance sampling schemes based on 'compressed genetrees'. The resulting schemes extend earlier work by Griffiths and Tavar\'e (1994), Stephens and Donnelly (2000), Birkner and Blath (2008) and Hobolth et. al. (2008). We conclude with a performance comparison o…
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.
Functional Type Error Control for Stabilised Space-Time IgA Approximations to Parabolic Problems
2018
The paper is concerned with reliable space-time IgA schemes for parabolic initial-boundary value problems. We deduce a posteriori error estimates and investigate their applicability to space-time IgA approximations. Since the derivation is based on purely functional arguments, the estimates do not contain mesh dependent constants and are valid for any approximation from the admissible (energy) class. In particular, they imply estimates for discrete norms associated with stabilised space-time IgA approximations. Finally, we illustrate the reliability and efficiency of presented error estimates for the approximate solutions recovered with IgA techniques on a model example.
The expressive power of the shuffle product
2010
International audience; There is an increasing interest in the shuffle product on formal languages, mainly because it is a standard tool for modeling process algebras. It still remains a mysterious operation on regular languages.Antonio Restivo proposed as a challenge to characterize the smallest class of languages containing the singletons and closed under Boolean operations, product and shuffle. This problem is still widely open, but we present some partial results on it. We also study some other smaller classes, including the smallest class containing the languages composed of a single word of length 2 which is closed under Boolean operations and shuffle by a letter (resp. shuffle by a l…
Fast Matrix Multiplication
2015
Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le~Gall has led to an improved algorithm running in time O(n2.3729). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n2.3725), and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078}); in particular, this approach cannot prove the conjecture that for every e > 0, …
Duality theory for multi-marginal optimal transport with repulsive costs in metric spaces
2018
In this paper we extend the duality theory of the multi-marginal optimal transport problem for cost functions depending on a decreasing function of the distance (not necessarily bounded). This class of cost functions appears in the context of SCE Density Functional Theory introduced in "Strong-interaction limit of density-functional theory" by M. Seidl.
On a class of languages with holonomic generating functions
2017
We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM
Frames for fusions of modal logics
2018
Let us consider multimodal logics and . We assume that is characterised by a class of connected frames, and there exists an -frame with a so-called -starting point. Similarly, the logic is characterised by a class of connected frames, and there exists an -frame with a -starting point. Using isomorphic copies of the frames and , we construct a connected frame which characterises the fusion . The frame thus obtained has some useful properties. Among others, is countable if both and are countable, and there is a special world of the frame such that any formula is valid in the frame if and only if it is valid at the point . We also describe a similar construction where we assume the existence o…
The ideal duplication
2021
AbstractIn this paper we present and study the ideal duplication, a new construction within the class of the relative ideals of a numerical semigroup S, that, under specific assumptions, produces a relative ideal of the numerical duplication $$S\bowtie ^b E$$ S ⋈ b E . We prove that every relative ideal of the numerical duplication can be uniquely written as the ideal duplication of two relative ideals of S; this allows us to better understand how the basic operations of the class of the relative ideals of $$S\bowtie ^b E$$ S ⋈ b E work. In particular, we characterize the ideals E such that $$S\bowtie ^b E$$ S ⋈ b E is nearly Gorenstein.
Local minimizers and gamma-convergence for nonlocal perimeters in Carnot groups
2020
We prove the local minimality of halfspaces in Carnot groups for a class of nonlocal functionals usually addressed as nonlocal perimeters. Moreover, in a class of Carnot groups in which the De Giorgi's rectifiability Theorem holds, we provide a lower bound for the $\Gamma$-liminf of the rescaled energy in terms of the horizontal perimeter.