Practical and flexible pattern matching over Ziv–Lempel compressed text

We address the problem of string matching on Ziv–Lempel compressed text. The goal is to search for a pattern in a text without uncompressing it. This is a highly relevant issue to keep compressed text databases where efficient searching is still possible. We develop a general technique for string matching when the text comes as a sequence of blocks. This abstracts the essential features of Ziv–Lempel compression. We then apply the scheme to each particular type of compression. We present an algorithm to find all the matches of a pattern in a text compressed using LZ77. When we apply our scheme to LZ78, we obtain a much more efficient search algorithm, which is faster than uncompressing the text and then searching it. Finally, we propose a new hybrid compression scheme which is between LZ77 and LZ78, being in practice as good to compress as LZ77 and as fast to search as LZ78. We show also how to search for some extended patterns on Ziv–Lempel compressed text, such as classes of characters and approximate string matching.     

Indexing text using the Ziv–Lempel trie

Let a text of u characters over an alphabet of size σ be compressible to n phrases by the LZ78 algorithm. We show how to build a data structure based on the Ziv–Lempel trie, called the LZ-index, that takes 4nlog₂n(1+o(1)) bits of space (that is, 4 times the entropy of the text for ergodic sources) and reports the R occurrences of a pattern of length m in worst case time O(m³logσ+(m+R)logn). We present a practical implementation of the LZ-index, which is faster than current alternatives when we take into consideration the time to report the positions or text contexts of the occurrences found.     

Regular expression searching on compressed text

We present a solution to the problem of regular expression searching on compressed text. The format we choose is the Ziv–Lempel family, specifically the LZ78 and LZW variants. Given a text of length u compressed into length n, and a pattern of length m, we report all the R occurrences of the pattern in the text in O(2^m+mn+Rmlogm) worst case time. On average this drops to O(m²+(n+Rm)logm) or O(m²+n+Ru/n) for most regular expressions. This is the first nontrivial result for this problem. The experimental results show that our compressed search algorithm needs half the time necessary for decompression plus searching, which is currently the only alternative.     

Approximate source conditions in Tikhonov–Phillips regularization and consequences for inverse problems with multiplication operators

The object of this paper is threefold. First, we investigate in a Hilbert space setting the utility of approximate source conditions in the method of Tikhonov–Phillips regularization for linear ill‐posed operator equations. We introduce distance functions measuring the violation of canonical source conditions and derive convergence rates for regularized solutions based on those functions. Moreover, such distance functions are verified for simple multiplication operators in L²(0, 1). The second aim of this paper is to emphasize that multiplication operators play some interesting role in inverse problem theory. In this context, we give examples of non‐linear inverse problems in natural sciences and stochastic finance that can be written as non‐linear operator equations in L²(0, 1), for which the forward operator is a composition of a linear integration operator and a non‐linear superposition operator. The Fréchet derivative of such a forward operator is a composition of a compact integration and a non‐compact multiplication operator. If the multiplier function defining the multiplication operator has zeros, then for the linearization an additional ill‐posedness factor arises. By considering the structure of canonical source conditions for the linearized problem it could be expected that different decay rates of multiplier functions near a zero, for example the decay as a power or as an exponential function, would lead to completely different ill‐posedness situations. As third we apply the results on approximate source conditions to such composite linear problems in L²(0, 1) and indicate that only integrals of multiplier functions and not the specific character of the decay of multiplier functions in a neighbourhood of a zero determine the convergence behaviour of regularized solutions. Copyright © 2005 John Wiley & Sons, Ltd.     

Traveling wave solutions of n‐dimensional delayed reaction–diffusion systems and application to four‐dimensional predator–prey systems

This paper deals with the existence of traveling wave solutions for n‐dimensional delayed reaction–diffusion systems. By using Schauder's fixed point theorem, we establish the existence result of a traveling wave solution connecting two steady states by constructing a pair of upper–lower solutions that are easy to construct. As an application, we apply our main results to a four‐dimensional delayed predator–prey system and obtain the existence of traveling wave solutions. Copyright © 2016 John Wiley & Sons, Ltd.     

Global existence of solutions to reaction–diffusion systems without conditions on the nonlinearities growth

It is well known that, for reaction–diffusion systems, if the nonlinearities grow faster than a polynomial, nothing seems to be known for instance. The purpose of this paper is to give sufficient conditions guaranteeing global existence, uniqueness and uniform boundedness of solutions for coupled reaction–diffusion equations without condition growth on the reactions terms f and g in case f + g ≠ 0. These systems possess many and various applications in physics as the diffusion of the Phosphorus in the Silicone or some models describing some nuclear reactions; there have also been other applications in chemistry and biology. Our techniques are based on the Lyapunov functional methods. Copyright © 2010 John Wiley & Sons, Ltd.     

A weak solution approach to a reaction–diffusion system modeling pattern formation on seashells

We investigate a reaction–diffusion system proposed by H. Meinhardt as a model for pattern formation on seashells. We give a new proof for the existence of a local weak solution for general initial conditions and parameters upon using an iterative approach. Furthermore, the solution is shown to exist globally for suitable initial data. The behavior of the solution in time and space is illustrated through numerical simulations. Copyright © 2009 John Wiley & Sons, Ltd.     

On the Frame–Stewart algorithm for the multi-peg Tower of Hanoi problem

It is proved that seven different approaches to the multi-peg Tower of Hanoi problem are all equivalent. Among them the classical approaches of Stewart and Frame from 1941 can be found.     

On compactness of the velocity field in the incompressible limit of the full Navier–Stokes–Fourier system on large domains

The incompressible limit for the full Navier–Stokes–Fourier system is studied on a family of domains containing balls of the radius growing with a speed that dominates the inverse of the Mach number. It is shown that the velocity field converges strongly to its limit locally in space, in particular, the effect of the sound waves is eliminated by means of the local decay estimates for the acoustic wave equation. Copyright © 2008 John Wiley & Sons, Ltd.     

Large‐time behaviour and blow up of solutions for Gierer–Meinhardt systems

The purpose of this paper is to give a proof of global existence of solutions for Gierer–Meinhardt systems with homogeneous Neumann boundary conditions. Our technique is based on Lyapunov functional argument that yields the uniform boundedness of solutions. The asymptotic behaviour of the solutions under suitable conditions is also studied. Moreover, under reasonable conditions on the exponents of the nonlinear term, we show the blow up in finite time of the solutions for the considered system. These results are valid for any positive initial data in , without any differentiability conditions. Copyright © 2016 John Wiley & Sons, Ltd.     

Joint additive Kullback–Leibler residual minimization and regularization for linear inverse problems

For the approximate solution of ill‐posed inverse problems, the formulation of a regularization functional involves two separate decisions: the choice of the residual minimizer and the choice of the regularizor. In this paper, the Kullback–Leibler functional is used for both. The resulting regularization method can solve problems for which the operator and the observational data are positive along with the solution, as occur in many inverse problem applications. Here, existence, uniqueness, convergence and stability for the regularization approximations are established under quite natural regularity conditions. Convergence rates are obtained by using an a priori strategy. Copyright © 2007 John Wiley & Sons, Ltd.     

Inverse scattering transform for the defocusing Ablowitz–Ladik system with arbitrarily large nonzero background

In this work we develop the inverse scattering transform (IST) for the defocusing Ablowitz–Ladik (AL) equation with arbitrarily a large nonzero background at space infinity. The IST was developed in previous works under the assumption that the amplitude of the background satisfies a “small norm” condition . On the other hand, Ohta and Yang recently showed that the defocusing AL system, which is modulationally stable for , becomes unstable if , and exhibits discrete rogue wave solutions, some of which are regular for all times. Here, we construct the IST for the defocusing AL with , analyze the spectrum, and characterize the soliton and rational solutions from a spectral point of view. We formulate the direct and inverse problems by using a suitable uniformization variable, and pose the inverse problem as an RHP across a simple contour in the complex plane of the uniform variable. As a by‐product of the IST, we also obtain explicit soliton solutions, which are the discrete analog of the celebrated Kuznetsov–Ma, Akhmediev, Peregrine solutions, and which mimic the corresponding solutions for the focusing AL equation. Soliton solutions that are the analog of the dark soliton solutions of the defocusing AL equation in the case are also presented.     

Clifford–Fourier transform on hyperbolic space

In this paper, we introduce a new generalization of the Helgason–Fourier transform using the angular Dirac operator on both the hyperboloid and unit ball models. The explicit integral kernels of even dimension are derived. Furthermore, we establish the formal generating function of the even dimensional kernels. In the computations, fractional integration plays a key unifying role. Copyright © 2016 John Wiley & Sons, Ltd.     

Fisher–KPP equation with advection on the half‐line

We consider the Fisher–KPP equation with advection: u_t=u_xx?βu_x+f(u) on the half‐line x∈(0,∞), with no‐flux boundary condition u_x?βu = 0 at x = 0. We study the influence of the advection coefficient ?β on the long time behavior of the solutions. We show that for any compactly supported, nonnegative initial data, (i) when β∈(0,c₀), the solution converges locally uniformly to a strictly increasing positive stationary solution, (ii) when β∈[c₀,∞), the solution converges locally uniformly to 0, here c₀ is the minimal speed of the traveling waves of the classical Fisher–KPP equation. Moreover, (i) when β > 0, the asymptotic positions of the level sets on the right side of the solution are (β + c₀)t + o(t), and (ii) when β≥c₀, the asymptotic positions of the level sets on the left side are (β ? c₀)t + o(t). Copyright © 2016 John Wiley & Sons, Ltd.     

A non‐existence result on Cameron–Liebler line classes

Cameron–Liebler line classes are sets of lines in PG(3, q) that contain a fixed number x of lines of every spread. Cameron and Liebler classified Cameron–Liebler line classes for x ∈ {0, 1, 2, q² ? 1, q², q² + 1} and conjectured that no others exist. This conjecture was disproven by Drudge for q = 3 [8] and his counterexample was generalized to a counterexample for any odd q by Bruen and Drudge [4]. A counterexample for q even was found by Govaerts and Penttila [9]. Non‐existence results on Cameron–Liebler line classes were found for different values of x. In this article, we improve the non‐existence results on Cameron–Liebler line classes of Govaerts and Storme [11], for q not a prime. We prove the non‐existence of Cameron–Liebler line classes for 3 ≤ x < q/2. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 342–349, 2008     

Laplace–Beltrami equation on hypersurfaces and Γ‐convergence

A mixed boundary value problem for the stationary heat transfer equation in a thin layer around a surface with the boundary is investigated. The main objective is to trace what happens in Γ‐limit when the thickness of the layer converges to zero. The limit Dirichlet BVP for the Laplace–Beltrami equation on the surface is described explicitly, and we show how the Neumann boundary conditions in the initial BVP transform in the Γ‐limit. For this, we apply the variational formulation and the calculus of Günter's tangential differential operators on a hypersurface and layers, which allow global representation of basic differential operators and of corresponding boundary value problems in terms of the standard Euclidean coordinates of the ambient space . Copyright © 2017 John Wiley & Sons, Ltd.     

Some maximal inequalities on Triebel–Lizorkin spaces for

In this work we give some maximal inequalities in Triebel–Lizorkin spaces, which are “‐variants” of Fefferman–Stein vector‐valued maximal inequality and Peetre's maximal inequality. We will give some applications of the new maximal inequalities and discuss sharpness of some results.     

A stabilized finite element method based on local polynomial pressure projection for the stationary Navier–Stokes equations

This article considers a stabilized finite element approximation for the branch of nonsingular solutions of the stationary Navier–Stokes equations based on local polynomial pressure projection by using the lowest equal-order elements. The proposed stabilized method has a number of attractive computational properties. Firstly, it is free from stabilization parameters. Secondly, it only requires the simple and efficient calculation of Gauss integral residual terms. Thirdly, it can be implemented at the element level. The optimal error estimate is obtained by the standard finite element technique. Finally, comparison with other methods, through a series of numerical experiments, shows that this method has better stability and accuracy.     

Rapid error reduction for block Gauss–Seidel based on p‐hierarchical basis

We consider a two‐level block Gauss–Seidel iteration for solving systems arising from finite element discretizations employing higher‐order elements. A p‐hierarchical basis is used to induce this block structure. Using superconvergence results normally employed in the analysis of gradient recovery schemes, we argue that a massive reduction of the H¹‐error occurs in the first iterate, so that the discrete solution is adequately resolved in very few iterates—sometimes a single iteration is sufficient. Numerical experiments on uniform and adapted meshes support these claims. Copyright © 2012 John Wiley & Sons, Ltd.