共查询到20条相似文献,搜索用时 31 毫秒
1.
For each nonempty binary word w= c1c2cq, where ci{0,1}, the nonnegative integer ∑ i=1q ( q+1− i) ci is called the moment of w and is denoted by M( w). Let [ w] denote the conjugacy class of w. Define M([ w])={ M( u): u[ w]}, N( w)={ M( u)− M( w): u[ w]} and δ( w)=max{ M( u)− M( v): u, v[ w]}. Using these objects, we obtain equivalent conditions for a binary word to be an -word (respectively, a power of an -word). For instance, we prove that the following statements are equivalent for any binary word w with | w|2: (a) w is an -word, (b) δ( w)=| w|−1, (c) w is a cyclic balanced primitive word, (d) M([ w]) is a set of | w| consecutive positive integers, (e) N( w) is a set of | w| consecutive integers and 0 N( w), (f) w is primitive and [ w] St. 相似文献
2.
We formulate a class of difference schemes for stiff initial-value problems, with a small parameter ε multiplying the first derivative. We derive necessary conditions for uniform convergence with respect to the small parameter ε, that is the solution of the difference scheme uih satisfies | uih− u( xi)| Ch, where C is independent of h and ε. We also derive sufficient conditions for uniform convergence and show that a subclass of schemes is also optimal in the sense that | uih− u( xi)| C min ( h, ε). Finally, we show that this class contains higher-order schemes. 相似文献
3.
For a system consisting of a set of sensors S = { S1, S2, …, Sm} and a set of objects O = { O1, O2, …, On}, there are information constraints given by a relation R S × O such that ( Si, Oj) R if and only if Si is capable of detecting Oj. Each ( Si, Oj) R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O( m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1; (b) uniform formulation where ( Si, Oj) R, for all Si S, Oj O; (c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection; (b) probabilistically independent detection; (c) decomposable systems under additive and nonfractional multiplicative measures; and (d) matroid systems. 相似文献
4.
A heap structure designed for secondary storage is suggested that tries to make the best use of the available buffer space in primary memory. The heap is a complete multi-way tree, with multi-page blocks of records as nodes, satisfying a generalized heap property. A special feature of the tree is that the nodes may be partially filled, as in B-trees. The structure is complemented with priority-queue operations insert and delete-max. When handling a sequence of S operations, the number of page transfers performed is shown to be O(∑ i = 1S(1/ P) log(M/P)( Ni/ P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and Ni, the number of records in the heap prior to the ith operation (assuming P 1 and S> M c · P, where c is a small positive constant). The number of comparisons required when handling the sequence is O(∑ i = 1S log2 Ni). Using the suggested data structure we obtain an optimal external heapsort that performs O(( N/ P) log(M/P)( N/ P)) page transfers and O( N log2 N) comparisons in the worst case when sorting N records. 相似文献
5.
A subdivision scheme for constructing smooth surfaces interpolating scattered data in R 3 is proposed. It is also possible to impose derivative constraints in these points. In the case of functional data, i.e., data are given in a properly triangulated set of points {( xi, yi)} i=1N from which none of the pairs ( xi, yi) and ( xj, yj) with i≠ j coincide, it is proved that the resulting surface (function) is C1. The method is based on the construction of a sequence of continuous splines of degree 3. Another subdivision method, based on constructing a sequence of splines of degree 5 which are once differentiable, yields a function which is C2 if the data are not ‘too irregular’. Finally the approximation properties of the methods are investigated. 相似文献
6.
A previous application of the Newton divided difference series of the displacement function Ez = (1 + Δ) z = e Dz, where the operators Δ and D are the variables, to purely exponential interpolation employing general-factorial differences and derivatives, {Pi; mi=0 (Δ - Si)} f(0) and {Pi; mi=0 ( D - ti)} f(0), in which the si's and ti's are distinct[1], is here extended to mixed polynomial-exponential interpolation where the si's and ti's are no longer distinct. 相似文献
7.
Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set { vii0} of (finite) words on A such that ƒ= v0v1… vi…, { vii1} is a biprefix code and vi≠ vj for positive integers i≠ j. 相似文献
8.
This paper presents a sum-of-product neural network (SOPNN) structure. The SOPNN can learn to implement static mapping that multilayer neural networks and radial basis function networks normally perform. The output of the neural network has the sum-of-product form ∑ Npi=1∏ Nvj=1 fij ( xj), where xj's are inputs, Nv is the number of inputs, fij( ) is a function generated through network training, and Np is the number of product terms. The function fij( xj) can be expressed as ∑ kwijkBjk( xj), where Bjk( ) is a single-variable basis function and Wijk's are weight values. Linear memory arrays can be used to store the weights. If Bjk( ) is a Gaussian function, the new neural network degenerates to a Gaussian function network. This paper focuses on the use of overlapped rectangular pulses as the basis functions. With such basis functions, WijkBjk( xj) will equal either zero or Wijk, and the computation of fij( xj) becomes a simple addition of some retrieved Wijk's. The structure can be viewed as a basis function network with a flexible form for the basis functions. Learning can start with a small set of submodules and have new submodules added when it becomes necessary. The new neural network structure demonstrates excellent learning convergence characteristics and requires small memory space. It has merits over multilayer neural networks, radial basis function networks and CMAC in function approximation and mapping in high-dimensional input space. The technique has been tested for function approximation, prediction of a time series, learning control, and classification. 相似文献
9.
In this paper, we consider coupled semi-infinite diffusion problems of the form ut( x, t)− A2 uxx( x, t) = 0, x> 0, t> 0, subject to u(0, t)= B and u( x,0)=0, where A is a matrix in
, and u( x, t), and B are vectors in
. Using the Fourier sine transform, an explicit exact solution of the problem is proposed. Given an admissible error and a domain D( x0, t0)={( x, t);0≤ x≤ x0, t≥ t0 > 0, an analytic approximate solution is constructed so that the error with respect to the exact solution is uniformly upper bounded by in D( x0, t0). 相似文献
10.
The aim of this paper is double. First, we point out that the hypothesis D( t1) D( t2) = D( t2) D( t1) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω( t0, t1) = [0, p] × [ t0, t1], for mixed problems of the type ut( x, t) − D( t) uxx( x, t) = 0, 0 < x < p, t> 0, subject to u(0, t) = u( p, t) = 0 and u( x,0) = F( x) is proposed. Here, u( x, t) and F( x) are r-component vectors, D( t) is a Cr × r valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) ( D( t) + D( t) H) is bigger than δ. An illustrative example is included. 相似文献
11.
In this paper we study the behavior of the beta-spline functions in the case the parameter β 2( i) is negative. We prove that a negative value
exists so that if
, the beta-spline functions Ni( u) are positive. Moreover, if the control vertices are such that x0 xm−1, we have proved that the design curve keeps the properties already proved in the case β 2( i) 0. 相似文献
12.
Let
be such that d1, pd=1, p02 and
. We are proving in this note a new criterion for the pair
to be a canonical number system. This enables us to prove that if p2,…, pd−1,∑ i=1dpi0 and p0>2∑ i=1d| pi|, then
is a canonical number system. 相似文献
13.
In finite element analysis, isoparametric mapping defined as [(ξ, η) → ( x, y): X = Niξ i] is widely used. It is a one-to-one mapping and its construction is especially elegant for elements of a variable number of nodes showing its versatile applicability to model curved boundaries. In certain analyses, such as remeshing in dynamic analyses or contouring and others, the inverse of this mapping is inevitably valuable, but its determination is not so straightforward. To avoid solving a system of nonlinear equations, generally an iterative technique of order N2 in a two-dimensional mesh is often resorted to. In the paper, this technique is improved by systematically bisecting along a predefined line that reduces the iterations to only order N. Its applications in remeshing and nodal quantity contouring are demonstrated and a possible extension for stress contouring is also discussed. The FORTRAN subroutines for the technique proposed are also given. 相似文献
14.
In (Röschel, l997) B-spline technique was used for blending of Lagrange interpolants. In this paper we generalize this idea replacing Lagrange by Hermite interpolants. The generated subspline b( t) interpolates the Hermite input data consisting of parameter values ti and corresponding derivatives ai,j, j=0,…, i−1, and is called blended Hermite interpolant (BHI). It has local control, is connected in affinely invariant way with the input and consists of integral (polynomial) segments of degree 2· k−1, where k−1max{ i}−1 denotes the degree of the B-spline basis functions used for the blending. This method automatically generates one of the possible interpolating subsplines of class Ck−1 with the advantage that no additional input data is necessary. 相似文献
15.
Consider the cubic sensor d x = d w, d y = x3d t + d v where w, v are two independent Brownian motions. Given a function φ( x) of the state x let φ t( x) denote the conditional expectation given the observations ys, 0 s t. This paper consists of a rather detailed discussion and outline of proof of the theorem that for nonconstant φ there cannot exist a recursive finite-dimensional filter for φ driven by the observations. 相似文献
16.
A review is carried out on the characterisation and algorithmic implementation of an extended product-form approximation, based on the principle of maximum entropy (ME), for a wide class of arbitrary finite capacity open queueing network models (QNMs) with service and space priorities. A single server finite capacity GE/GE/1/N queue with R ( R>1) distinct priority classes, compound Poisson arrival processes (CPPs) with geometrically distributed batches and generalised exponential (GE) service times is analysed via entropy maximisation, subject to suitable GE-type queueing theoretic constraints, under preemptive resume (PR) and head-of-line (HOL) scheduling rules combined with complete buffer sharing (CBS) and partial buffer sharing (PBS) management schemes stipulating a sequence of buffer thresholds {N=( N1,…, NR),0< Ni≤ Ni−1, i=2,…, R}. The GE/GE/1/N queue is utilised, in conjunction with GE-type first two moment flow approximation formulae, as a cost-effective building block towards the establishment of a generic ME queue-by-queue decomposition algorithm for arbitrary open QNMs with space and service priorities under repetitive service blocking with random destination (RS-RD). Typical numerical results are included to illustrate the credibility of the ME algorithm against simulation for various network topologies and define experimentally pessimistic GE-type performance bounds. Remarks on the extensions of the ME algorithm to other types of blocking mechanisms, such as repetitive service blocking with fixed destination (RS-FD) and blocking-after-service (BAS), are included. 相似文献
17.
We call a function f in n variables an order-configuration function if for any x1,…, xn such that xi1 … xin we have f( x1,…, xn) = xt, where t is determined by the n-tuple ( i1,…, in) corresponding to that ordering. Equivalently, it is a function built as a minimum of maxima, or a maximum of minima. Well-known examples are the minimum, the maximum, the median, and more generally rank functions, or the composition of rank functions. Such types of functions are often used in nonlinear processing of digital signals or images (for example in the median or separable median filter, min-max filters, rank filters, etc.). In this paper we study the mathematical properties of order-configuration functions and of a wider class of functions that we call order-subconfiguration functions. We give several characterization theorems for them. We show through various examples how our concepts can be used in the design of digital signal filters or image transformations based on order-configuration functions. 相似文献
18.
建立基于凸优化方法重构矩阵信号X=[x 1,…,x n]的一组充分条件,X具有列稀疏性和平坦性的结构特征,即每个列向量x j至多具有s个非零分量、同时所有列向量的l 1范数具有相同数值。所采用的矩阵范数是■。工作分两部分,第一部分分别对无观测误差和有观测误差的情况,针对求解■型凸优化问题重构以上类型矩阵信号的方法,建立保障稳定性和鲁棒性的充分条件;第二部分工作建立随机观测情况下观测空间维数的下界,用以保证信号以高概率被正确重构。所得结果优于将重构向量信号的min-l 1方法直接推广到针对矩阵信号的min-l 1方法所得到的结果,并给出数值仿真验证。所针对的信号模型出现在具有定常或缓变包络波形的多输入/多输出雷达及合成孔径雷达等新应用领域,本文工作针对这类应用提供一组实用的信号重构条件。 相似文献
19.
This paper presents an efficient algorithm for enumerating all minimal a- b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = ( V, E), Our algorithm requires O( n3Rab) time, which improves the known result of O( n4Rab) time for solving this problem, where ¦ V¦= n and Rab is the number of minimal a- b separators. The algorithm can be generalized for enumerating all minimal A- B separators that separate non-adjacent vertex sets A, B < V, and it requires O( n2( n − nA − nb) RAB) time in this case, where na = ¦ A¦, nB = ¦ B¦ and rAB is the number of all minimal A− B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O( n3R+Σ + n4RΣ), which improves the known result of O( n6RΣ) time, where Rσ is the number of all minimal separators of G and RΣR+Σ = ∑ 1i, v j) ER vivj (n( n − 1)/2 − m) RΣ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O(( n/ log n) Rab) time and the second one runs in time O(( n/ log n) R+Σ+ n log nRΣ) on a CREW PRAM with O( n3) processors. 相似文献
20.
For an ordered set W = { w1, w2,…, wk} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r( v | W) = ( d( v, w1), d( v, w2),…, d( v, wk)), where d( x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented. A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim+(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim+(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim+(G) = res(G) = n − 1 if and only if G = Kn, while dim+(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle. The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim+(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim+(G) ≥ N and dim+(G) − dim(G) ≥ N. 相似文献
|