FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

Generalized lattice model of liquid state and its relation to Ginzburg–Landau theory

Basic principles of the generalized lattice model of multicomponent condensed systems are formulated. Short-range parts of interatomic interactions are taken into account by means of the geometric constraints method. Long-range parts of the interactions are taken into account in mean field approximation. The expression for Helmholtz free energy is obtained. A system of integral equations for the equilibrium distributions of components is derived. The asymptotic properties of its solutions are investigated. Moment expansion of interatomic interactions and localization of integral terms in free energy is obtained. A Ginzburg–Landau-like functional of free energy is derived.     

Structure and electrochemical behaviour of 4,7-diazaheptyl-trimethoxy-silane and vinyl-trialkoxy-silane adsorbed at silver surface

Novel self-assembled monolayers were obtained on silver using 4,7-diazaheptyl-trimethoxy-silane (SiN) and vinyl-trialkoxy-silane (SiVA, where the alkyl group is 3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57,60-eicozaoxa- hexaheptaconan). It was shown that thus modified metal surface was protected against electrooxidation. A densely packed monolayer remained stable and did not desorb from the Ag electrode on the potential cycling. The structure of SiN and SiVA as well as their complexes with Li⁺ cations were calculated and visualised by the AM1d and PM5 semi-empirical methods.     

Propriétés statistiques des entiers friables

Let Ψ(x,y) (resp. Ψ_m(x,y)) denote the number of integers not exceeding x that are y-friable, i.e. have no prime factor exceeding y (resp. and are coprime to m). Evaluating the ratio Ψ_m(x/d,y)/Ψ(x,y) for 1≤slantd≤slantx, m≥slant 1, x≥slant y≥slant 2, turns out to be a crucial step for estimating arithmetic sums over friable integers. Here, it is crucial to obtain formulae with a very wide range of validity. In this paper, several uniform estimates are provided for the aforementioned ratio, which supersede all previously known results. Applications are given to averages of various arithmetic functions over friable integers which in turn improve corresponding results from the literature. The technique employed rests mainly on the saddle-point method, which is an efficient and specific tool for the required design.2000 Mathematics Subject Classification: Primary—11N25; Secondary—11K65, 11N37     

具有急慢性阶段的MSIS流行病模型阈值和稳定性结果

系统研究了具有急性和慢性两个阶段的MSIS流行病模型.由两节构成,第1节建立和研究了具有急慢性阶段的MSIS流行病模型;第2节在第1节的基础上建立和研究了具有慢性病病程的MSIS流行病模型.第1节的模型是四个常微分方程构成的方程组.第2节的模型既含有常微分方程,又含有偏微分方程.运用微分方程和积分方程中的理论和方法,得到了这两个模型再生数R0的表达式.证明了当R0<1时,无病平衡态是全局渐近稳定性,给出了各模型地方病平衡态的存在性和稳定性条件.     

Analysis of a 2D “liquid”plasma lattice

Adustyplasmacanbedefinedasacomplicatedplasmacontainingsmallsolidmattercalleddustgrainsordustparticles,whichareusuallychargednegatively,duetoelectronshighermobilitythanion,bycollectingelectronsandionsfromthebackgroundplasma.Theuniverseisfilledwithdustyplasmassuchasplanetaryrings,comettails,andnebulae.Also,inindustrialplasmaprocessing,particulatessuspendedinplasmaarethemajorcontaminationinsemiconductormanufacture.Studiesondustyplasmahavebeenextendedtofar-flungtopicssuchaswaves,instabilities,stro…     

Feedback controlled periodic states for different kinds of photorefractive nonlinear response

We investigate analytically and numerically the influence of the type of the photorefractive nonlinear response on the periodic states (attractors) which occur during feedback controlled 2W-coupling and correspond to almost 100% diffraction efficiency of the dynamic index grating. In addition to the case of the local response typical, for example, for LiNbO₃ crystals we consider the cases of nonlocal (diffusive) response (BaTiO₃, SBN) and resonant response (DC-biased BSO, BTO, and BGO crystals). It is shown that the conditions for the transition to the periodic states and their apparent characteristics are strongly different for the two limiting cases above. Received 16 July 2002 / Received in final form 29 October 2002 Published online 4 March 2003     

A theoretical study of the ion pair SN2 reaction between lithium isocyanates with methyl fluoride with inversion and retention mechanism

This paper is devoted to a detailed theoretical study of an ion pair S_N2 reaction LiNCO+CH₃F in the gas phase and in solution at the level of MP2(full)/6-31+G**//HF/6-31+G**. Two possible reaction mechanisms, inversion and retention, are discussed. There are eight possible reaction pathways. The inversion mechanism is more favorable no matter in the gas phase or in solution based on analyses of the transition structures. Methyl isocyanate should form preferentially in the gas phase and more stable methyl cyanate is the main product in solution. The retardation of the reaction in solvents was attributed to the difference in solvation in the separated reactants and in the transition state.     

Phenylene dendrimers and novel hyperbranched polyphenylenes as light emissive materials for blue OLEDs

New materials based on low-generation polyphenylene dendrimers with the light emission in the blue spectrum range were synthesized and examined for an efficient organic light emitting diodes (OLED) application. It has been shown that the ratio of p-phenylene groups with high fluorescence parameters to 1,3,5-triphenylbenzene groups with low fluorescent parameters may be the possible reason for the experimental variations of relative quantum yield of photoluminescence in the compounds explored. The quantum yield value is increased with a number of dendrimer generations up to 50–70%. The role of bromine atoms as the luminescence quenchers have been demonstrated, which is important for synthesis route choice.     

广义Sierpinski集

本文考察了包括平面上的各种广义 Cantor集 ,Sierpinski集和包括某些连续不可微曲线在内的广义 Sierpinski集 .由相似变换 ,导出了它们的级数表达式 ,并利用它和字符串空间的对应关系 ,计算出它们的Hausdorff维数