On a special class of primitive words

When representing DNA molecules as words, it is necessary to take into account the fact that a word u encodes basically the same information as its Watson-Crick complement θ(u), where θ denotes the Watson-Crick complementarity function. Thus, an expression which involves only a word u and its complement can be still considered as a repeating sequence. In this context, we define and investigate the properties of a special class of primitive words, called pseudo-primitive words relative to θ or simply θ-primitive words, which cannot be expressed as such repeating sequences. For instance, we prove the existence of a unique θ-primitive root of a given word, and we give some constraints forcing two distinct words to share their θ-primitive root. Also, we present an extension of the well-known Fine and Wilf theorem, for which we give an optimal bound.     

On the number of frames in binary words

A frame is a square uu, where u is an unbordered word. Let F(n) denote the maximum number of distinct frames in a binary word of length n. We count this number for small values of n and show that F(n) is at most ⌊n/2⌋+8 for all n and greater than 7n/30−? for any positive ? and infinitely many n. We also show that Fibonacci words, which are known to contain plenty of distinct squares, have only a few frames. Moreover, by modifying the Thue-Morse word, we prove that the minimum number of occurrences of frames in a word of length n is ⌈n/2⌉−2.     

Modified nonlinearly dispersive mK(m,n,k) equations: I. New compacton solutions and solitary pattern solutions

In this paper exact solutions of the modified nonlinearly dispersive KdV equations (simply called mK(m,n,k) equations), u^m−1u_t+a(uⁿ)_x+b(u^k)_xxx=0, are investigated by using some direct ansatze. As a result, abundant new compacton solutions: solitons with the absence of infinite wings, solitary pattern solutions having infinite slopes or cups, solitary wave solutions and periodic wave solutions are obtained.     

A study of nonlinear dispersive equations with solitary-wave solutions having compact support

With the use of Adomian decomposition method, the prototypical, genuinely nonlinear K(m,n) equation, u_t+(u^m)_x+(uⁿ)_xxx=0, which exhibits compactons — solitons with finite wavelength — is solved exactly. Two numerical illustrations, K(2,2) and K(3,3), are investigated to illustrate the pertinent features of the proposed scheme. The technique is presented in a general way so that it can be used in nonlinear dispersive equations.     

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.     

New compacton soliton solutions and solitary patterns solutions of nonlinearly dispersive Boussinesq equations

The special exact solutions of nonlinearly dispersive Boussinesq equations (called B(m,n) equations), u_tt−u_xx−a(uⁿ)_xx+b(u^m)_xxxx=0, is investigated by using four direct ansatze. As a result, abundant new compactons: solitons with the absence of infinite wings, solitary patterns solutions having infinite slopes or cups, solitary waves and singular periodic wave solutions of these two equations are obtained. The variant is extended to include linear dispersion to support compactons and solitary patterns in the linearly dispersive Boussinesq equations with m=1. Moreover, another new compacton solution of the special case, B(2,2) equation, is also found.     

A simple nc algorithm to recognize weakly triangulated graphs

Let S be a set of n closed intervals on the x-axis. A ranking assigns to each interval, s, a distinct rank, p(s)? [1, 2,…,n]. We say that s can see t if p(s)<p(t) and there is a point p?s∩t so that p?u for all u with p(s)<p(u)<p(t). It is shown that a ranking can be found in time O(n log n) such that each interval sees at most three other intervals. It is also shown that a ranking that minimizes the average number of endpoints visible from an interval can be computed in time O(n ^5/2). The results have applications to intersection problems for intervals, as well as to channel routing problems which arise in layouts of VLSI circuits.     

Diagnosable evaluation of DCC linear congruential graphs under the PMC diagnostic model

A DCC (disjoint consecutive cycles) linear congruential graph G(F, n) consists of n nodes and is generated by a set of linear functions F with special properties. It was proved that G(F, n) is a 2t-regular graph and has connectivity 2t, where t=|F| and 1?t?p-1 (n=2^p for some integer p). For a multiprocessor system, its diagnosability is critical to measure the performance. In this paper, we study the diagnosability of G(F,2^p) under the precise and pessimistic diagnosis strategies based on the PMC (Preparata, Metze, and Chien) diagnostic model. It is proved that G(F,2^p) is 2t-diagnosable and (4t-5)/(4t-5)-diagnosable under the two diagnosis strategies, respectively, where p?3 and 2?t?p-1. In addition, the diagnosability of DCC linear congruential graphs is compared with that of BC (bijective connection) graphs.     

Cycles embedding in exchanged hypercubes

The exchanged hypercube EH(s,t), proposed by Loh et al., is obtained by systematically removing links from a binary hypercube. This paper investigates important properties related to embedding cycles into the exchanged hypercube EH(s,t). The authors show that EH(1,t) and EH(2,2) are not bipancyclic, but EH(s,t) (2?s?t) except EH(2,2) is bipancyclic and EH(s,t) (3?s?t) is vertex-bipancyclic. Moreover, every edge of EH(s,t) (2?s?t) lies on an even l-cycle where 8?l?²s+t+1.     

Compressed Word Problems in HNN-extensions and?Amalgamated Products

It is shown that the compressed word problem for an HNN-extension ??H,t?Ot ^?1 at=?(a) (a??A)?? with A finite is polynomial time Turing-reducible to the compressed word problem for the base group H. An analogous result for amalgamated free products is shown as well.     

Computing maximal-exponent factors in an overlap-free word

The exponent of a word is the quotient of its length over its smallest period. The exponent and the period of a word can be computed in time proportional to the word length. We design an algorithm to compute the maximal exponent of all factors of an overlap-free word. Our algorithm runs in linear-time on a fixed-size alphabet, while a naive solution of the question would run in cubic time. The solution for non-overlap-free words derives from algorithms to compute all maximal repetitions, also called runs, occurring in the word.We also show there is a linear number of occurrences of maximal-exponent factors in an overlap-free word. Their maximal number lies between 0.66n and 2.25n in a word of length n. The algorithm can additionally locate all of them in linear time.     

Time-space trade-offs for compressed suffix arrays

Given a binary string of length n, we give a representation of its suffix array that takes O(nt(lgn)^1/t) bits of space such that given i,1?i?n, the ith entry in the suffix array of the string can be retrieved in O(t) time, for any parameter 1?t?lglgn. For t=lglgn, this gives a compressed suffix array representation of Grossi and Vitter [Proc. Symp. on Theory Comput., 2000, pp. 397-406]. For t=O(1/ε), this gives the best known (in terms of space) compressed suffix array representation with constant query time. From this representation one can construct a suffix tree structure for a text of length n, that uses o(nlgn) bits of space which can be used to find all the k occurrences of a given pattern of length m in O(m/lgn+k) time. No such structure was known earlier.     

Characterization of analytic phase signals

In many cases, a real-valued signal χ(t) may be associated with a complex-valued signal a(t)e^iθ(t), the analytic signal associated with χ(t) with the characteristic properties χ(t) = a(t) cosθ(t) and H(a(·)cosθ(·))(t) = a(t)sinθ(t). Using such obtained amplitude-frequency modulation the instantaneous frequency of χ(t) at the time t₀ may be defined to be θ′(t₀), provided θ′(t₀) ≥ 0. The purpose of this note is to characterize, in terms of analytic functions, the unimodular functions F(t) = C(t) + iS(t),C²(t) + S² (t) = 1, a.e., that satisfy HC(t) = S(t). This corresponds to the case a(t) ≡ 1 in the above formulation. We show that a unimodular function satisfies the required condition if and only if it is the boundary value of a so called inner function in the upper-half complex plane. We also give, through an explicit formula, a large class of functions of which the parametrization C(t) = cosθ(t) is available and the extra condition θ′(t) ≥ 0, a.e. is enjoyed. This class of functions contains Blaschke products in the upper-half complex plane as a proper subclass studied by Picinbono in [1].     

On multiplication in algebraic extension fields

In this paper we characterize all algorithms for obtaining the coefficients of (Σ^n?1_i=0x_iuⁱ)(Σ^n?1_i=0y_iuⁱ) mod P(u), where P(u) is an irreducible po lynomial of degree n, which use 2n ? 1 multiplications. It is shown that up to equivalence, all such algorithms are obtainable by first obtaining the coefficients of the product of two polynomials, and then reducing modulo the irreducible polynomial.     

Double solutions of boundary value problems for 2mth-order differential equations and difference equations

A double fixed-point theorem is applied to obtain the existence of at least two positive solutions for the boundary value problem, (−1)^my^(2m)(t) = f(y(t)), t ϵ [0, 1], y⁽²ⁱ⁾(0) = y⁽²ⁱ⁺¹⁾(1) = 0, 0 ≤ i ≤ m−1. It is later applied to obtain the existence of at least two positive solutions for the analogous discrete boundary value problem, (−1)^mΔ^2mu(k) = g(u(k)), k ϵ {0, …, N}, Δ²ⁱu(0) = Δ²ⁱ⁺¹u(N + 1) = 0, 0 ⩽ m − 1.     

Time-Bounded Kolmogorov Complexity and Solovay Functions

A Solovay function is an upper bound g for prefix-free Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n. We obtain natural examples of computable Solovay functions by showing that for some constant c ₀ and all computable functions t such that c ₀ n??t(n), the time-bounded version K ^t of K is a Solovay function. By unifying results of Bienvenu and Downey and of Miller, we show that a right-computable upper bound g of K is a Solovay function if and only if ?? _g =??2^?g(n) is Martin-Löf random. We obtain as a corollary that the Martin-Löf randomness of the various variants of Chaitin??s ?? extends to the time-bounded case in so far as $\Omega _{ \textnormal{K}^{t}}$ is Martin-Löf random for any t as above. As a step in the direction of a characterization of K-triviality in terms of jump-traceability, we demonstrate that a set A is K-trivial if and only if A is O(g(n)?K(n))-jump traceable for all computable Solovay functions g. Furthermore, this equivalence remains true when the universal quantification over all computable Solovay functions in the second statement is restricted either to all functions of the form K ^t for some function t as above or to a single function K ^t of this form. Finally, we investigate into the plain Kolmogorov complexity C and its time-bounded variant C ^t of initial segments of computably enumerable sets. Our main theorem here asserts that every high c.e. Turing degree contains a c.e. set B such that for any computable function t there is a constant c _t >0 such that for all m it holds that C ^t (B?m)??c _t ?m, whereas for any nonhigh c.e. set A there is a computable time bound t and a constant c such that for infinitely many m it holds that C ^t (A?m)??logm+c. By similar methods it can be shown that any high degree contains a set B such that C ^t (B?m)??⁺ m/4. The constructed sets B have low unbounded but high time-bounded Kolmogorov complexity, and accordingly we obtain an alternative proof of the result due to Juedes et al. (Theor. Comput. Sci. 132(1?C2):37?C70, 1994) that every high degree contains a strongly deep set.     

On Word Equations in One Variable

For a word equation E of length n in one variable x occurring # _x times in E a resolution algorithm of O(n+# _x log n) time complexity is presented here. This is the best result known and for the equations that feature #_x < \fracnlogn\#_{x}<\frac{n}{\log n} it yields time complexity of O(n) which is optimal. Additionally it is proven here that the set of solutions of any one-variable word equation is either of the form F or of the form F∪(uv)⁺ u where F is a set of O(log n) words and u, v are some words such that uv is a primitive word.     

Parabolic equations with double variable nonlinearities

The paper is devoted to the study of the homogeneous Dirichlet problem for the doubly nonlinear parabolic equation with nonstandard growth conditions:

ut=div(a(x,t,u)|u^|α(x,t)|∇u^|p(x,t)−2∇u)+f(x,t)     

Approximate solution for a variable-coefficient semilinear heat equation with nonlocal boundary conditions

This paper develops an iterative algorithm for the solution to a variable-coefficient semilinear heat equation with nonlocal boundary conditions in the reproducing space. It is proved that the approximate sequence u _n (x, t) converges to the exact solution u(x, t). Moreover, the partial derivatives of u _n (x, t) are also convergent to the partial derivatives of u(x, t). And the approximate sequence u _n (x, t) is the best approximation under a complete normal orthogonal system.     

A new critical theorem for adaptive nonlinear stabilization

It is fairly well known that there are fundamental differences between adaptive control of continuous-time and discrete-time nonlinear systems. In fact, even for the seemingly simple single-input single-output control system y_t+1=θ₁f(y_t)+u_t+w_t+1 with a scalar unknown parameter θ₁ and noise disturbance {w_t}, and with a known function f(⋅) having possible nonlinear growth rate characterized by |f(x)|=Θ(|x|^b) with b≥1, the necessary and sufficient condition for the system to be globally stabilizable by adaptive feedback is b<4. This was first found and proved by Guo (1997) for the Gaussian white noise case, and then proved by Li and Xie (2006) for the bounded noise case. Subsequently, a number of other types of “critical values” and “impossibility theorems” on the maximum capability of adaptive feedback were also found, mainly for systems with known control parameter as in the above model. In this paper, we will study the above basic model again but with additional unknown control parameter θ₂, i.e., u_t is replaced by θ₂u_t in the above model. Interestingly, it turns out that the system is globally stabilizable if and only ifb<3. This is a new critical theorem for adaptive nonlinear stabilization, which has meaningful implications for the control of more general uncertain nonlinear systems.