Oscillatory behavior of delay partial difference equations with positive and negative coefficients

We construct an important transform to obtain sufficient conditions for the oscillation of all solutions of delay partial difference equations with positive and negative coefficients of the form A_m+1,n + A_m,n+1 − A_mn + p_mnA_m−k−1 − q_mnA_{m−k′,n−l′} = 0, where m, n = 0, 1, …, and k, k′, l′, l are nonnegative integers, p, q ϵ (0, ∞), the coefficients {q_mn} and {p_mn} are sequences of nonnegative real numbers.     

Expansion of Self-Similar Functions in the Faber–Schauder System

Let Ω = A^N be a space of right-sided infinite sequences drawn from a finite alphabet A = {0,1}, N = {1,2,…}. Let ρ(x, y)Σ_k=1^∞|x _k ? y _k |2^?k be a metric on Ω = AN, and μ the Bernoulli measure on Ω with probabilities p₀, p₁ > 0, p₀ + p₁ = 1. Denote by B(x,ω) an open ball of radius r centered at ω. The main result of this paper \(\mu (B(\omega ,r))r + \sum\nolimits_{n = 0}^\infty {\sum\nolimits_{j = 0}^{{2^n} - 1} {{\mu _{n,j}}} } (\omega )\tau ({2^n}r - j)\), where τ(x) = 2min {x,1 ? x}, 0 ≤ x ≤ 1, (τ(x) = 0, if x < 0 or x > 1 ), \({\mu _{n,j}}(\omega ) = (1 - {p_{{\omega _{n + 1}}}})\prod _{k = 1}^n{p_{{\omega _k}}} \oplus {j_k}\), \(j = {j_1}{2^{n - 1}} + {j_2}{2^{n - 2}} + ... + {j_n}\). The family of functions 1, x, τ(2 ⁿ r ? j), j = 0,1,…, 2 ⁿ ? 1, n = 0,1,…, is the Faber–Schauder system for the space C([0,1]) of continuous functions on [0, 1]. We also obtain the Faber–Schauder expansion for Lebesgue’s singular function, Cezaro curves, and Koch–Peano curves. Article is published in the author’s wording.     

A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

Let X and Y be two strings of lengths n and m, respectively, and k and l, respectively, be the numbers of runs in their corresponding run-length encoded forms. We propose a simple algorithm for computing the longest common subsequence of two given strings X and Y in O(kl+min{p₁,p₂}) time, where p₁ and p₂ denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. It improves the previously known time bound O(min{nl,km}) and outperforms the time bounds O(kllogkl) or O((k+l+q)log(k+l+q)) for some cases, where q denotes the number of matched blocks.     

Asymptotic behavior of nonoscillatory solutions of neutral difference equations

The authors consider the m^th-order neutral difference equation D_m(y(n) + p(n)y(n − k) + q(n)f(y(σ(n))) = e(n), where m ≥ 1, {p(n)}, {q(n)}, {e(n)}, and {a₁(n)}, {a₂(n)}, …, {a_m−1(n)} are real sequences, a_i(n) > 0 for i = 1,2,…, m−1, a_m(n) ≡ 1, D₀z(n) = y(n)+p(n)y(n − k), D_iz(n) = a_i(n)ΔD_i−1z(n) for i = 1,2, …, m, k is a positive integer, {σ(n)} → ∞ is a sequence of positive integers, and R → R is continuous with u f(u) > 0 for u ≠ 0. In the case where {q(n)} is allowed to oscillate, they obtain sufficient conditions for all bounded nonoscillatory solutions to converge to zero, and if {q(n)} is a nonnegative sequence, they establish sufficient conditions for all nonoscillatory solutions to converge to zero. Examples illustrating the results are included throughout the paper.     

Oscillation and nonoscillation for second-order linear difference equations

New oscillation and nonoscillation theorems are obtained for the second-order linear difference equation Δ²x_n−1 + p_nx_n = 0, where if p_n^∞_n=1 is a real sequence with p_n ≥ 0.     

Monoid-labeled transition systems

Given a -complete (semi)lattice , we consider -labeled transition systems as coalgebras of a functor ⁽⁻⁾, associating with a set X the set ^X of all -fuzzy subsets. We describe simulations and bisimulations of -coalgebras to show that L⁽⁻⁾ weakly preserves nonempty kernel pairs iff it weakly preserves nonempty pullbacks iff L is join infinitely distributive (JID).Exchanging for a commutative monoid , we consider the functor ⁽⁻⁾_ω which associates with a set X all finite multisets containing elements of X with multiplicities m M. The corresponding functor weakly preserves nonempty pullbacks along injectives iff 0 is the only invertible element of , and it preserves nonempty kernel pairs iff is refinable, in the sense that two sum representations of the same value, r₁ + … + r_m = c₁ + … + c_n, have a common refinement matrix (m_{(i, j)}) whose k-th row sums to r_k and whose l-th column sums to c_l for any 1≤ k ≤ m and 1 ≤ l ≤ n.     

Controllability of general nonlinear systems

Consider the nonlinear system $$\dot x(t) = f(x(t)) + \sum\limits_{i = 1}^m {u_i (t)g_i (x(t)), x(0) = x_0 \in M}$$ whereM is aC ^∞ realn-dimensional manifold,f, g ₁,?.,g _m areC ^∞ vector fields onM, andu ₁ ,..,u _m are real-valued controls. Ifm=n?1 andf, g ₁ ,?,g _m are linearly independent, then the system is called a hypersurface system, and necessary and sufficient conditions for controllability are known. For a generalm, 1 ≤m ≤n?1, and arbitraryC ^∞ vector fields,f, g ₁ ,?,g _m , assume that the Lie algebra generated byf, g ₁ ,?,g _m and by taking successive Lie brackets of these vector fields is a vector bundle with constant fiber (vector space) dimensionp onM. By Chow's Theorem there exists a maximalC ^∞ realp-dimensional submanifoldS ofM containingx ₀ with the generated bundle as its tangent bundle. It is known that the reachable set fromx ₀ must contain an open set inS. The largest open subsetU ofS which is reachable fromx ₀ is called the region of reachability fromx ₀. IfO is an open subset ofS which is reachable fromx ₀,S we find necessary conditions and sufficient conditions on the boundary ofO inS so thatO = U. Best results are obtained when it is assumed that the Lie algebra generated byg ₁,?,g _m and their Lie brackets is a vector bundle onM.     

Polylogarithms and the Asymptotic Formula for the Moments of Lebesgue’s Singular Function

Recall that Lebesgue’s singular function L(t) is defined as the unique solution to the equation L(t) = qL(2t) + pL(2t ? 1), where p, q > 0, q = 1 ? p, p ≠ q. The variables M _n = ∫₀¹t ⁿ dL(t), n = 0,1,… are called the moments of the function The principal result of this work is \({M_n} = {n^{{{\log }_2}p}}{e^{ - \tau (n)}}(1 + O({n^{ - 0.99}}))\), where the function τ(x) is periodic in log₂x with the period 1 and is given as \(\tau (x) = \frac{1}{2}1np + \Gamma '(1)lo{g_2}p + \frac{1}{{1n2}}\frac{\partial }{{\partial z}}L{i_z}( - \frac{q}{p}){|_{z = 1}} + \frac{1}{{1n2}}\sum\nolimits_{k \ne 0} {\Gamma ({z_k})L{i_{{z_k} + 1}}( - \frac{q}{p})} {x^{ - {z_k}}}\), \({z_k} = \frac{{2\pi ik}}{{1n2}}\), k ≠ 0. The proof is based on poissonization and the Mellin transform.     

Large deviations for distributions of sums of random variables: Markov chain method

Let {ξ _k } _k=0^∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} $ P\left\{ {\frac{1} {n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\} , n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely, the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables with g(x) = |x| ^p , p > 0, and exponential random variables with g(x) = x for x ≥ 0.     

New upper and lower bounds for the eigenvalues of the Sturm-Liouville problem

We derive new inequalities for the eigenvaluesλ _k of the Sturm-Liouville problem?u″+qu=λu, u(0)=u(π)=0 under the usual hypothesis thatq has mean value zero. The estimates give upper and lower bounds of the form |λ _k ?k ²|≤p _1,m k ^?m +P _2,m k ^2m ,k ²≥3‖q‖ _m ,m=1, 2 where ‖q‖ _m is the norm ofq in a Sobolev spaceH ^m (0, π) and theP's are homogeneous polynomials of degree at most 3 in ‖q‖ _m . Such bounds are used in the analysis of the inverse Sturm-Liouville problem.     

Asymmetric quantum Reed-Solomon and generalized Reed-Solomon codes

Two new families of asymmetric quantum codes are constructed in this paper. The first one is derived from the Calderbank-Shor-Steane (CSS) construction applied to classical Reed-Solomon (RS) codes, providing quantum codes with parameters [[N = l(q ^l −1), K = l(q ^l −2d + c + 1), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power and d > c + 1, c ≥ 1, l ≥ 1 are integers. The second family is derived from the CSS construction applied to classical generalized RS codes, generating quantum codes with parameters [[N = mn, K = m(2k−n + c), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power, 1 < k < n < 2k + c ≤ q ^m , k = n − d + 1, and n, d > c + 1, c ≥ 1, m ≥ 1 are integers. Although the second proposed construction generalizes the first one, the techniques developed in both constructions are slightly different. These new codes have parameters better than or comparable to the ones available in the literature. Additionally, the proposed codes can be utilized in quantum channels having great asymmetry, that is, quantum channels in which the probability of occurrence of phase-shift errors is large when compared to the probability of occurrence of qudit-flip errors.     

Simple and Improved Parameterized Algorithms for Multiterminal Cuts

Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min?(n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: $O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))Given a graph G=(V,E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 ^l kT(n,m)) time and Vertex Multiterminal Cut can be solved in O(k ^l T(n,m)) time, where T(n,m)=O(min (n ^2/3,m ^1/2)m) is the running time of finding a minimum (s,t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 ^l T(n,m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 ^l T(n,m)), O(2.772 ^l T(n,m)), O(3.349 ^l T(n,m)) and O(3.857 ^l T(n,m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: O((min(?{2k},l)+1)^2k2^lT(n,m))O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m)) -time algorithm for Edge Multicut and O((2k) ^k+l/2 T(n,m))-time algorithm for Vertex Multicut.     

Multiple serial episodes matching

Given q+1 strings (a text t of length n and q patterns m₁,…,mq) and a natural number w, the multiple serial episode matching problem consists in finding the number of size w windows of text t which contain patterns m₁,…,mq as subsequences, i.e., for each mi, if mi=p₁,…,pk, the letters p₁,…,pk occur in the window, in the same order as in mi, but not necessarily consecutively (they may be interleaved with other letters). Our main contribution here is an algorithm solving this problem on-line in time O(nq) with an MP-RAM model (which is a RAM model equipped with extra operations).     

Stability and absolute stability of a three-point difference scheme

Consider a three-point difference scheme −h⁻²Δ⁽²⁾y_n + q_n(h)y_n = f_n(h), n ϵ Z = {0, ±1, ±2, …}, where h ϵ (0, h₀], h₀ is a given positive number, Δ⁽²⁾y_n = y_n+1 + y_n−1, f(h) = {f_n(h)}_{n ϵ Z} ϵ L_∞(h), L_∞(h) = {f(h) : ∥f(h)∥_L∞(h) < ∞}, ∥f(h)∥_L∞(h) = sup_nϵZ ∥f_n(h)∥.We assume a unique a priori requirement 0 <- q_n(h) < ∞ for any n ϵ Z and h ϵ (0, h₀]. The main results are a criterion of stability and absolute stability of the difference scheme (1) in the space L_∞(h).     

Set-contractive mappings and difference equations in Banach spaces

In this paper, we consider the difference equation on an arbitrary Banach space (X, ∥·∥_x), Δ(q_nΔx_n + f_n(x_n) = 0, where {q_n} is a positive sequence and f_n is X-valued. We shall give conditions so that for a given x ϵ X, there exists a solution of this equation asymptotically equal to x.     

Maximum number of edges joining vertices on a cube

Let E_d(n) be the number of edges joining vertices from a set of n vertices on a d-dimensional cube, maximized over all such sets. We show that E_d(n)=∑_i=0^r−1(l_i/2+i)2^l_i, where r and l₀>l₁>?>l_r−1 are nonnegative integers defined by n=∑_i=0^r−12^l_i.     

New results for oscillation of delay difference equations

In this paper, we consider the delay difference equation x_n+1 − x_n + p_nx_n−k = 0, n = 0, 1, 2, …, where p_n is a sequence of nonnegative real numbers and k is a positive integer. Some new results for the oscillation of this equation are obtained. Our theorems improve all known results in the literature.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^1.5k ?^?1.5k (α(n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, α is the inverse Ackermann function, and ? ≤ 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ?) times the weight of a minimum weight complete matching.     

On linear interpolation under interval data

Some results related to the problem of interpolation of n vertical segments (x_k, Y_k), k = 1,…,n, in the plane with generalized polynomial functions that are linear combinations of m basic functions are presented. It is proved that the set of interpolating functions (if not empty) is bounded in every subinterval (x_k, x_k+1) by two unique such functions η_k⁻ and η_k⁺. An algorithm with result verification for the determination of the boundary functions η_k⁻, η_k⁺ and for their effective tabulation is reported and some examples are discussed.