共查询到20条相似文献,搜索用时 46 毫秒
1.
Local constraints on an infinite sequence that imply global regularity are of general interest in combinatorics on words. We consider this topic by studying everywhere α-repetitive sequences. Such a sequence is defined by the property that there exists an integer N≥2 such that every length-N factor has a repetition of order α as a prefix. If each repetition is of order strictly larger than α, then the sequence is called everywhere α+-repetitive. In both cases, the number of distinct minimal α-repetitions (or α+-repetitions) occurring in the sequence is finite.A natural question regarding global regularity is to determine the least number, denoted by M(α), of distinct minimalα-repetitions such that an α-repetitive sequence is not necessarily ultimately periodic. We call the everywhere α-repetitive sequences witnessing this property optimal. In this paper, we study optimal 2-repetitive sequences and optimal 2+-repetitive sequences, and show that Sturmian words belong to both classes. We also give a characterization of 2-repetitive sequences and solve the values of M(α) for 1≤α≤15/7. 相似文献
2.
Zhi-Wei Sun 《Journal of Algebra》2001,240(2):223
A residue class a + n
with weight λ is denoted by λ, a, n. For a finite system
= {λs, as, ns}ks = 1 of such triples, the periodic map w
(x) = ∑ns|x − as λs is called the covering map of
. Some interesting identities for those
with a fixed covering map have been known; in this paper we mainly determine all those functions f : Ω →
such that ∑ks = 1 λsf(as + ns
) depends only on w
where Ω denotes the family of all residue classes. We also study algebraic structures related to such maps f, and periods of arithmetical functions ψ(x) = ∑ks = 1 λse2πiasx/ns and ω(x) = |{1 ≤ s ≤ k : (x + as, ns) = 1}|. 相似文献
3.
Let φ be a one-dimensional surjective cellular automaton map. We prove that if φ is a closing map, then the configurations which are both spatially and temporally periodic are dense. (If φ is not a closing map, then we do not know whether the temporally periodic configurations must be dense.) The results are special cases of results for shifts of finite type, and the proofs use symbolic dynamical techniques. 相似文献
4.
We study a class of inverse monoids of the form M=Inv 〈X∣w=1〉, where the single relator w has a combinatorial property that we call sparse. For a sparse word w, we prove that the word problem for M is decidable. We also show that the set of words in (X∪X
−1)* that represent the identity in M is a deterministic context free language, and that the set of geodesics in the Schützenberger graph of the identity of M is a regular language. 相似文献
5.
For a stationary autoregressive process of order p and disturbance variance σ2 it is shown that the determinant of the covariance of T (≥p) consecutive random variables of the process is (σ2)T Πi,j=1p (1 − wiwj)−1, where w1, …, wp are the roots of the associated polynomial equation. 相似文献
6.
We study the Hamiltonian system (HS)
where H ε C2 (
2N,
) satisfies H (0) = 0, H′ (0) = 0 and the quadratic form
) is non-degenerate. We fix τ0 > 0 and assume that
2N E F decomposes into linear subspaces E and F which are invariant under the flow associated to the linearized system (LHS)
= JH″ (0) x and such that each solution of (LHS) in E is τ0-periodic whereas no solution of (LHS) in F − 0 is τ0-periodic. We write σ(τ0) = σQ(τ0) for the signature of the quadratic form Q restricted to E. If σ(τ0) ≠ 0 then there exist periodic solutions of (HS) arbitrarily close to 0. More precisely we show, either there exists a sequence xk → 0 of τk-periodic orbits on the energy level H−1 (0) with τk → τ0; or for each λ close to 0 with λσ(τ0) > 0 the energy level H−1 (λ) contains at least
distinct periodic orbits of (HS) near 0 with periods near τ0. This generalizes a result of Weinstein and Moser who assumed QE to be positive definite. 相似文献
7.
Maxime Crochemore Costas S. Iliopoulos Gonzalo Navarro Yoan J. Pinzon Alejandro Salinger 《Journal of Discrete Algorithms》2005,3(2-4):198-214
(δ,γ)-matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P1…m and a text T1…n on an alphabet of integers, find the occurrences P′ of the pattern in the text such that (i) , and (ii) . The problem makes sense for δγδm. Several techniques for (δ,γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mnlog(γ)/w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mnlog(δm)/w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ. 相似文献
8.
In this paper we study the existence of periodic solutions of the fourth-order equations uiv − pu″ − a(x)u + b(x)u3 = 0 and uiv − pu″ + a(x)u − b(x)u3 = 0, where p is a positive constant, and a(x) and b(x) are continuous positive 2L-periodic functions. The boundary value problems (P1) and (P2) for these equations are considered respectively with the boundary conditions u(0) = u(L) = u″(0) = u″(L) = 0. Existence of nontrivial solutions for (P1) is proved using a minimization theorem and a multiplicity result using Clark's theorem. Existence of nontrivial solutions for (P2) is proved using the symmetric mountain-pass theorem. We study also the homoclinic solutions for the fourth-order equation uiv + pu″ + a(x)u − b(x)u2 − c(x)u3 = 0, where p is a constant, and a(x), b(x), and c(x) are periodic functions. The mountain-pass theorem of Brezis and Nirenberg and concentration-compactness arguments are used. 相似文献
9.
Giuseppe Pirillo 《Annals of Combinatorics》2008,12(1):115-121
For any infinite word r over A = {a, b} we associate two infinite words min(r), max(r) such that any prefix of min(r) (max(r), respectively) is the lexicographically smallest (greatest, respectively) among the factors of r of the same length. We prove that (min(r); max(r)) = (as, bs) for some infinite word s if and only if r is a proper Sturmian word or an ultimately periodic word of a particular form. This result is based on a lemma concerning
sequences of infinite words.
Received July 11, 2005 相似文献
10.
Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A?=A∪{?}, where ? stands for a hole and matches (or is compatible with) every letter in A. The subword complexity of a partial word w, denoted by pw(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f:N→N is (k,h)-feasible if for each integer N≥1, there exists a k-ary partial word w with h holes such that pw(n)=f(n) for all n such that 1≤n≤N. We show that when dealing with feasibility in the context of finite binary partial words, the only affine functions that need investigation are f(n)=n+1 and f(n)=2n. It turns out that both are (2,h)-feasible for all non-negative integers h. We classify all minimal partial words with h holes of order N with respect to f(n)=n+1, called Sturmian, computing their lengths as well as their numbers, except when h=0 in which case we describe an algorithm that generates all minimal Sturmian full words. We show that up to reversal and complement, any minimal Sturmian partial word with one hole is of the form ai?ajbal, where i,j,l are integers satisfying some restrictions, that all minimal Sturmian partial words with two holes are one-periodic, and that up to complement, ?(aN−1?)h−1 is the only minimal Sturmian partial word with h≥3 holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n, showing them tight for h=0,1 or 2. 相似文献
11.
We study the structure of invertible substitutions on three-letter alphabet. We show that there exists a finite set
of invertible substitutions such that any invertible substitution can be written as Iwσ1σ2σk, where Iw is the inner automorphism associated with w, and
for 1jk. As a consequence, M is the matrix of an invertible substitution if and only if it is a finite product of non-negative elementary matrices. 相似文献
12.
J. Musielak 《Journal of Approximation Theory》1987,50(4)
Let l be a generalized Orlicz sequence space generated by a modular (x) = ∑i − 0∞ i(¦ti¦), X = (ti), with s-convex functions i, 0 < s 1, and let Kw,j: R+ → R+ for j=0,1,2,…, w ε Wwhere
is an abstract set of indices. Assuming certain singularity assumptions on the nonlinear kernel Kw,j and setting Twx = ((Twx)i)i = 0∞, with (Twx)i = ∑j = 0i Kw,i − j(¦tj¦) for x = (tj), convergence results: Twx → x in l are obtained (both modular convergence and norm convergence), with respect to a filter
of subsets of the set
. 相似文献
13.
The paper is devoted to the properties of infinite permutations. We introduce the infinite permutation ξ, in some sense similar to the period doubling word w (which is the fixed point of the morphism φw:00100,10101). We investigate combinatorial properties of ξ and find the complexity of ξ. 相似文献
14.
T.S. Quek 《Journal of Mathematical Analysis and Applications》1997,210(2):742
We extend the Littlewood–Paley theorem toLpw(G), whereGis a locally compact Vilenkin group andware weights satisfying the MuckenhouptApcondition. As an application we obtain a mixed-norm type multiplier result onLpw(G) and prove the sharpness of our result. We also obtain a sufficient condition for φ L∞(Γ) to be a multiplier on the power weightedLpα(G) in terms of its smoothness condition. 相似文献
15.
Let (X, Y) be an
d ×
-valued random vector and let (X1, Y1),…,(XN, YN) be a random sample drawn from its distribution. Divide the data sequence into disjoint blocks of length l1, …, ln, find the nearest neighbor to X in each block and call the corresponding couple (Xi*, Yi*). It is shown that the estimate mn(X) = Σi = 1n wniYi*/Σi = 1n wni of m(X) = E{Y|X} satisfies E{|mn(X) − m(X)|p}
0 (p ≥ 1) whenever E{|Y|p} < ∞, ln
∞, and the triangular array of positive weights {wni} satisfies supi ≤ nwni/Σi = 1n wni
0. No other restrictions are put on the distribution of (X, Y). Also, some distribution-free results for the strong convergence of E{|mn(X) − m(X)|p|X1, Y1,…, XN, YN} to zero are included. Finally, an application to the discrimination problem is considered, and a discrimination rule is exhibited and shown to be strongly Bayes risk consistent for all distributions. 相似文献
16.
Kyung Joong Kim Ronald Cools L. Gr. Ixaru 《Journal of Computational and Applied Mathematics》2002,140(1-2)
We consider the integral of a function
and its approximation by a quadrature rule of the formi.e., by a rule which uses the values of both y and its derivative at nodes of the quadrature rule. We examine the cases when the integrand is either a smooth function or an ω dependent function of the form y(x)=f1(x) sin(ωx)+f2(x) cos(ωx) with smoothly varying f1 and f2. In the latter case, the weights wk and αk are ω dependent. We establish some general properties of the weights and present some numerical illustrations. 相似文献
17.
We consider a positive self-adjoint operator A and formal rank one perturbations B = A + α(φ, ·)φ, where φ
−2(A) but φ
−1 (A), with
s(A) the usual scale of spaces. We show that B can be defined for such φ and what are essentially negative infinitesimal values of α. In a sense we will make precise, every rank one perturbation is one of three forms: (i) φ
−1(A), α
; (ii) φ
−1, α = ∞; or (iii) the new type we consider here. 相似文献
18.
Duran A. J. 《Journal of Approximation Theory》1993,74(3)
The subspaces Gα, Gβ, and Gβα (α, β ≥ 0)of Schwartz′ space S+ in (0, + ∞) are associated with the Hankel transform in the same way as the Gel′fand-Shilov spaces Sα, Sβ, and Sβα are associated with the Fourier transform. Indeed, if we consider the Hankel transform Hγ (γ < −1) defined by
γ(ƒ)(t) =
∫∞0 (xt)−γ/2xγJγ([formula]) ƒ(x) dx then
γ is an isomorphism from Gα, Gβ, and Gβα onto Gα, Gβ, and Gαβ respectively. So. the spaces Gαα are invariant for
γ. In this paper, we characterize the spaces Gαα (α > 1) in terms of their Fourier-Laguerre coefficients. Also, we characterize the range of the Fourier-Laplace operator
D defined by
D(ƒ)(w) = ∫∞0 ƒ(t) e−(1/2)((1 + w)/(1 − w))t for w D = {w
: |w| ≤ 1} when it acts on the space Gαα. 相似文献
19.
Maria Skopina 《Journal of Approximation Theory》2000,104(2):361
We investigate expansions of periodic functions with respect to wavelet bases. Direct and inverse theorems for wavelet approximation in C and Lp norms are proved. For the functions possessing local regularity we study the rate of pointwise convergence of wavelet Fourier series. We also define and investigate the “discreet wavelet Fourier transform” (DWFT) for periodic wavelets generated by a compactly supported scaling function. The DWFT has one important advantage for numerical problems compared with the corresponding wavelet Fourier coefficients: while fast computational algorithms for wavelet Fourier coefficients are recursive, DWFTs can be computed by explicit formulas without any recursion and the computation is fast enough. 相似文献
20.
Dragan Juki 《Journal of Approximation Theory》2009,156(2):212-222
For the given data (wi,xi,yi), i=1,…,M, we consider the problem of existence of the best discrete approximation in lp norm (1≤p<∞) by reciprocals of real polynomials. For this problem, the existence of best approximations is not always guaranteed. In this paper, we give a condition on data which is necessary and sufficient for the existence of the best approximation in lp norm. This condition is theoretical in nature. We apply it to obtain several other existence theorems very useful in practice. Some illustrative examples are also included. 相似文献