共查询到20条相似文献,搜索用时 46 毫秒
1.
Weimin Chen 《Journal of Algorithms in Cognition, Informatics and Logic》1998,26(2):370-385
Given two ordered trees and , the tree inclusion problem is to determine whether it is possible to obtain from by deleting nodes. Recently, this problem has been recognized as an important primitive in query processing for structured text databases. In this paper we present anO(|leaves()| ||) time andO(|leaves()|min(depth(), |leaves()|)) space algorithm for ordered tree inclusion, by means of a sophisticated bottom-up-matching strategy. Our algorithm improves the previous best one (Kilpeläinen, 1992, Ph.D. thesis, Dept. Computer Science, Univ. Helsinki) that requiresO(|| ||) time andO(||min(depth(), |leaves()|)) space. 相似文献
2.
Pao-Sheng Shen 《Statistics & probability letters》1998,40(4):87-361
Stute and Wang (1994) considered the problem of estimating the integral Sθ = ∫ θ dF, based on a possibly censored sample from a distribution F, where θ is an F-integrable function. They proposed a Kaplan-Meier integral to approximate Sθ and derived an explicit formula for the delete-1 jackknife estimate . differs from only when the largest observation, X(n), is not censored (δ(n) = 1 and next-to-the-largest observation, X(n-1), is censored (δ(n-1) = 0). In this note, it will pointed out that when X(n) is censored is based on a defective distribution, and therefore can badly underestimate . We derive an explicit formula for the delete-2 jackknife estimate . However, on comparing the expressions of and , their difference is negligible. To improve the performance of and , we propose a modified estimator according to Efron (1980). Simulation results demonstrate that is much less biased than and and . 相似文献
3.
We study the local-in-time regularity of the Brownian motion with respect to localized variants of modulation spaces and Wiener amalgam spaces . We show that the periodic Brownian motion belongs locally in time to and for (s−1)q<−1, and the condition on the indices is optimal. Moreover, with the Wiener measure μ on T, we show that and form abstract Wiener spaces for the same range of indices, yielding large deviation estimates. We also establish the endpoint regularity of the periodic Brownian motion with respect to a Besov-type space . Specifically, we prove that the Brownian motion belongs to for (s−1)p=−1, and it obeys a large deviation estimate. Finally, we revisit the regularity of Brownian motion on usual local Besov spaces , and indicate the endpoint large deviation estimates. 相似文献
4.
On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification 总被引:1,自引:0,他引:1
Let be identically distributed random vectors in Rd, independently drawn according to some probability density. An observation is said to be a layered nearest neighbour (LNN) of a point if the hyperrectangle defined by and contains no other data points. We first establish consistency results on , the number of LNN of . Then, given a sample of independent identically distributed random vectors from Rd×R, one may estimate the regression function by the LNN estimate , defined as an average over the Yi’s corresponding to those which are LNN of . Under mild conditions on r, we establish the consistency of towards 0 as n→∞, for almost all and all p≥1, and discuss the links between rn and the random forest estimates of Breiman (2001) [8]. We finally show the universal consistency of the bagged (bootstrap-aggregated) nearest neighbour method for regression and classification. 相似文献
5.
Zuoxiang Peng Lunfeng Cao Saralees Nadarajah 《Journal of multivariate analysis》2010,101(10):2641-2647
Let be a sequence of d-dimensional stationary Gaussian vectors, and let denote the partial maxima of . Suppose that there are missing data in each component of and let denote the partial maxima of the observed variables. In this note, we study two kinds of asymptotic distributions of the random vector where the correlation and cross-correlation satisfy some dependence conditions. 相似文献
6.
Sarah H. Ferguson 《Journal of Functional Analysis》1997,150(2):526-543
Results on first order Ext groups for Hilbert modules over the disk algebra are used to study certain backward shift invariant operator ranges, namely de Branges–Rovnyak spaces and a more general class called (W; B) spaces. Necessary and sufficient conditions are given for the groups Ext1A()(, (W; B)) to vanish whereis thedualof the vector-valued Hardy module, H2. One condition involves an extension problem for the Hankel operator with symbolB,ΓB, but viewed as a module map from H2into (W; B). The group Ext1A()(, (W; B))=(0) precisely whenΓBextends to a module map from L2into (W; B) and this in turn is equivalent to the injectivity of (W; B) in the category of contractive HilbertA()-modules. This result applied to the de Branges–Rovnyak spaces yields a connection between the extension problem for the HankelΓB and the operator corona problem. 相似文献
7.
Bob Coecke 《Journal of Mathematical Analysis and Applications》1998,220(2):603
We propose a representationr : ∪ Ω → ν, where is the collection of closed subspaces of ann-dimensional real, complex, or quaternionic Hilbert space , or equivalently, the projection lattice of this Hilbert space, where Ω is the set of all states ω : → [0, 1]. The value that ω ∈ Ω takes ina ∈ is given by the scalar product of the representative points (r(a) andr(ω)). The representationr(a ∨ b) of the join of two orthogonal elementsa, b ∈ is equal tor(a) + r(b). The convex closure of the representation of Σ, the set of atoms of , is equal to the representation of Ω. 相似文献
8.
Biagio Ricceri 《Nonlinear Analysis: Theory, Methods & Applications》2011,74(18):7446-7454
In this paper, we complete the refinement process, made by Ricceri (2009) [4], of a result established by Ricceri (2000) [1], which is one of the most applied abstract multiplicity theorems in the past decade. A sample of application of our new result is as follows.Let (n≥3) be a bounded domain with smooth boundary and let .Then, for each ?>0 small enough, there exists λ?>0 such that, for every compact interval , there exists ρ>0 with the following property: for every λ∈[a,b] and every continuous function satisfying for some , there exists δ>0 such that, for each ν∈[0,δ], the problem has at least three weak solutions whose norms in are less than ρ. 相似文献
9.
Ghislain Fourier 《Advances in Mathematics》2009,222(3):1080-1293
We provide combinatorial models for all Kirillov-Reshetikhin crystals of nonexceptional type, which were recently shown to exist. For types , , we rely on a previous construction using the Dynkin diagram automorphism which interchanges nodes 0 and 1. For type we use a Dynkin diagram folding and for types , a similarity construction. We also show that for types and the analog of the Dynkin diagram automorphism exists on the level of crystals. 相似文献
10.
For 0≤k≤n, let be the entries in Euler’s difference table and let . Dumont and Randrianarivony showed equals the number of permutations on [n] whose fixed points are contained in {1,2,…,k}. Rakotondrajao found a combinatorial interpretation of the number in terms of k-fixed-points-permutations of [n]. We show that for any n≥1, the sequence is essentially 2-log-concave and reverse ultra log-concave. 相似文献
11.
Stefan Hetzl Alexander Leitsch Daniel Weller 《Annals of Pure and Applied Logic》2011,162(12):1001-1034
We define a generalization of the first-order cut-elimination method CERES to higher-order logic. At the core of lies the computation of an (unsatisfiable) set of sequents (the characteristic sequent set) from a proof π of a sequent S. A refutation of in a higher-order resolution calculus can be used to transform cut-free parts of π (the proof projections) into a cut-free proof of S. An example illustrates the method and shows that can produce meaningful cut-free proofs in mathematics that traditional cut-elimination methods cannot reach. 相似文献
12.
In this note, it is shown that there exists a natural metric on the set[formula]of bounded subsets of containing their infimum which endowsTwith the structure of an -tree so that, for everyt∈T, the “number” of connected components ofT\{t} coincides with the cardinality #() of the set of subsets of . In addition, the set of ends ofTis explicitly determined, and various further features ofTare discussed, too. 相似文献
13.
In this paper we derive some irrationality and linear independence results for series of the form where is either a non-negative integer sequence with υn = o(log n/log log n) or a non-decreasing integer sequence with . 相似文献
14.
We obtain endpoint estimates for the Schrödinger operator f→eitΔf in with initial data f in the homogeneous Sobolev space . The exponents and regularity index satisfy and . For n=2 we prove the estimates in the range q>16/5, and for n?3 in the range q>2+4/(n+1). 相似文献
15.
Edge choosability and total choosability of planar graphs with no 3-cycles adjacent 4-cycles 总被引:1,自引:0,他引:1
Two cycles are said to be adjacent if they share a common edge. Let G be a planar graph without triangles adjacent 4-cycles. We prove that if Δ(G)≥6, and and if Δ(G)≥8, where and denote the list edge chromatic number and list total chromatic number of G, respectively. 相似文献
16.
François Genoud Bryan P. Rynne 《Nonlinear Analysis: Theory, Methods & Applications》2011,74(18):7269-7284
In this paper, we consider the eigenvalue problem consisting of the equation where and λ∈R, together with the multi-point boundary conditions where m±?1 are integers, and, for i=1,…,m±, , , with , . We show that if the coefficients are sufficiently small (depending on r), then the spectral properties of this problem are similar to those of the usual separated problem, but if the coefficients are not sufficiently small, then these standard spectral properties need not hold. The spectral properties of such multi-point problems have been obtained before for the constant coefficient case (r≡1), but the variable coefficient case has not been considered previously (apart from the existence of ‘principal’ eigenvalues).Some nonlinear multi-point problems are also considered. We obtain a (partial) Rabinowitz-type result on global bifurcation from the eigenvalues, and various nonresonance conditions for the existence of general solutions and also of nodal solutions—these results rely on the spectral properties of the linear problem. 相似文献
17.
Burcu Baran 《Journal of Number Theory》2010,130(12):2753-2772
Let be the open non-cuspidal locus of the modular curve associated to the normalizer of a non-split Cartan subgroup of level n. As Serre pointed out, an imaginary quadratic field of class number one gives rise to an integral point on for suitably chosen n. In this note, we give a genus formula for the modular curves and we give three new solutions to the class number one problem using the modular curves for n=16,20,21. These are the only such modular curves of genus ?2 that had not yet been exploited. 相似文献
18.
LetGbe a connected compact type Lie group equipped with anAdG-invariant inner product on the Lie algebra ofG. Given this data there is a well known left invariant “H1-Riemannian structure” on =(G)—the infinite dimensional group of continuous based loops inG. Using this Riemannian structure, we define and construct a “heat kernel”νT(g0, ·) associated to the Laplace–Beltrami operator on (G). HereT>0,g0∈(G), andνT(g0,·) is a certain probability measure on (G). For fixedg0∈(G) andT>0, we use the measureνT(g0,·) and the Riemannian structure on (G) to construct a “classical” pre-Dirichlet form. The main theorem of this paper asserts that this pre-Dirichlet form admits a logarithmic Sobolev inequality. 相似文献
19.
The Schur sufficiency condition for boundedness of any integral operator with non-negative kernel betweenL2-spaces is deduced from an observation, Proposition 1.2, about the central role played byL2-spaces in the general theory of these operators. Suppose (Ω, , μ) is a measure space and thatK: Ω×Ω→[0, ∞) is an ×-measurable kernel. The special case of Proposition 1.2 for symmetrical kernels says that such a linear integral operator is bounded onanyreasonable normed linear spaceXof -measurable functions only if it is bounded onL2(Ω, , μ) where its norm is no larger. The general form of Schur's condition (Halmos and Sunder “Bounded Integral Operators onL2-Spaces,” Springer-Verlag, Berlin/New York, 1978) is a simple corollary which, in the symmetrical case, says that the existence of an -measurable (not necessarily square-integrable) functionh>0μ-almost-everywhere onΩwithimplies thatKis a bounded (self-adjoint) operator onL2(Ω, , μ) of norm at mostΛ. When (Ω, , μ) isσ-finite, we show that Schur's condition is sharp: in the symmetrical case the boundedness of onL2(Ω, , μ) implies, for anyΛ>‖‖2, the existence of a functionh∈L2(Ω, , μ) which is positiveμ-almost-everywhere and satisfies (*). Such functionshsatisfying (*), whether inL2(Ω, , μ) or not, will be calledSchur test functions. They can be found explicitly in significant examples to yield best-possible estimates of the norms for classes of integral operators with non-negative kernels. In the general theory the operators are not required to be symmetrical (a theorem of Chisholm and Everitt (Proc. Roy. Soc. Edinburgh Sect. A69(14) (1970/1971), 199–204) on non-self-adjoint operators is derived in this way). They may even act between differentL2-spaces. Section 2 is a rather substantial study of how this method yields the exact value of the norm of a particular operator between differentL2-spaces which arises naturally in Wiener–Hopf theory and which has several puzzling features. 相似文献
20.
Let p be a prime number. The p-adic case of the Mixed Littlewood Conjecture states that for all α∈R. We show that with the additional factor of the statement is false. Indeed, our main result implies that the set of α for which is of full dimension. The result is obtained as an application of a general framework for Cantor sets developed in this paper. 相似文献