Effect of the Reynolds number on streamline bifurcations in a double-lid-driven cavity with free surfaces

The two-dimensional Navier-Stokes equations for a Newtonian fluid in the absence of body forces are considered in a rectangular double-lid-driven cavity with free surface side walls, the cavity aspect ratio A and three cases of the ratio (S=0,−1,1) of the upper to the lower lid speed. Using a finite element formulation with a mesh which is adaptively refined to facilitate the location of stagnation points, the effect of Reynolds numbers (Re) in the range [0,100] on the streamline patterns and their bifurcations is investigated as A is varied for each S. For Re→0 and each S as A is decreased, a sequence of pitchfork bifurcations at a stagnation point on x=0 is identified as seen in the work of Gaskell et al. [Proc Instn Mech Engrs Sci Part C 212 (1998) 387]. As Re increases for S=0 and decreasing A the stagnation point on x=0 disappears and away from x=0 cusp (saddle-node) bifurcations arise rather than the pitchfork bifurcation whereas for S=−1 and Re∈[0,100] the origin is always a stagnation point at which the same type of bifurcations arises.     

On relativizing auxiliary pushdown machines

We consider relativizing the constructions of Cook in [4] characterizing space-bounded auxiliary pushdown automata in terms of timebounded computers. LetS(n) ≥ logn be a measurable space bound. LetDT ^A[NT^A] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [nondeterministic] oracle Turing machine acceptor that runs in time 2 ^cS(n) for some constantc. LetDB _i ^A [NB _i ^A ] be the class of setsS such that there exists a machineM such thatM with oracleA recognizes the setS andM is a deterministic [non-deterministic] oracle Turing machine acceptor with auxiliary pushdown that runs in spaceS(n) and never queries the oracle about strings longer than:S(n) ifi = 1, 2 ^cS(n) for some constantc, ifi = 2, + ∞ ifi = 3. Then we prove the following results: These contrast with Cook's (unrelativized) result:DT = NB = DB.     

Categorical aspects of data type constructors

Sketches are introduced as presentations of many-sorted algebraic theories and data types are described as initial algebras for such sketches. A construction A⁺ofB is described where A⁺ is a suitably structured sketch and B is a sketch. In this construction each operation from A⁺ operates on all the sorts of B. Many examples are given. The two main theoretical results are the theorem about the tensor product ⊗ for structured sketches such that A⁺of(B⁺of C)≃(A⁺⊗B⁺)of C (Theorem 3.17), and the “homomorphism” theorem 4.2 which describes the operation of structured sketches on the fibred category of all models of all sketches.     

Online version of the theorem of Thue

A sequence S is nonrepetitive if no two adjacent blocks of S are the same. In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences over 3 symbols. We consider the online variant of this result in which a nonrepetitive sequence is constructed during a play between two players: Bob is choosing a position in a sequence and Alice is inserting a symbol on that position taken from a fixed set A. The goal of Bob is to force Alice to create a repetition, and if he succeeds, then the game stops. The goal of Alice is naturally to avoid that and thereby to construct a nonrepetitive sequence of any given length.We prove that Alice has a strategy to play arbitrarily long provided the size of the set A is at least 12. This is the online version of the theorem of Thue. The proof is based on nonrepetitive colorings of outerplanar graphs. On the other hand, one can prove that even over 4 symbols Alice has no chance to play for too long. The minimum size of the set of symbols needed for the online version of Thue?s theorem remains unknown.     

On the use of parallel processors for implicit Runge-Kutta methods

An iteration scheme, for solving the non-linear equations arising in the implementation of implicit Runge-Kutta methods, is proposed. This scheme is particularly suitable for parallel computation and can be applied to any method which has a coefficient matrixA with all eigenvalues real (and positive). For such methods, the efficiency of a modified Newton scheme may often be improved by the use of a similarity transformation ofA but, even when this is the case, the proposed scheme can have advantages for parallel computation. Numerical results illustrate this. The new scheme converges in a finite number of iterations when applied to linear systems of differential equations, achieving this by using the nilpotency of a strictly lower triangular matrixS ^?1 AS — Λ, with Λ a diagonal matrix. The scheme reduces to the modified Newton scheme whenS ^?1 AS is diagonal.A convergence result is obtained which is applicable to nonlinear stiff systems.     

Wavelet-based detection of crop zinc stress assessment using hyperspectral reflectance

Accurate detection of heavy metal-induced stress on the growth of crops is essential for agricultural ecological environment and food security. This study focuses on exploring singularity parameters as indicators for a crop's Zn stress level assessment by applying wavelet analysis to the hyperspectral reflectance. The field in which the experiment was conducted is located in the Changchun City, Jilin Province, China. The hyperspectral and biochemistry data from four crops growing in Zn contaminated soils: rice, maize, soybean and cabbage were collected. We performed a wavelet transform to the hyperspectral reflectance (350-1300 nm), and explored three categories of singularity parameters as indicators of crop Zn stress, including singularity range (S_R), singularity amplitude (S_A) and a Lipschitz exponent (α). The results indicated that (i) the wavelet coefficient of the fifth decomposition level by applying Daubechies 5 (db5) mother wavelets proved successful for identifying crop Zn stress; the S_R of crop concentrated on the region was around 550-850 nm of the spectral signal under Zn stress; (ii) the S_R stabilized, but S_A and α had developed some variations at the growth stages of the crop; (iii) the S_R, S_A and α were found among four crop species differentially; and moreover the S_A increased in relation to an increase in the S_R of crop species; (iv) the α had a strong non-linear relationship with the Zn concentration (R²:0.7601-0.9451); the S_A had a strong linear relationship with Zn concentration (R²:0.5141-0.8281). Singularity parameters can be used as indicators for a crop's Zn stress level as well as offer a quantitative analysis of the singularity of spectrum signal. The wavelet transform technique has been shown to be very promising in detecting crops with heavy metal stress.     

How good is the information theory bound in sorting?

We define a sorting problem on an n element set S to be a family 〈A₁,…,A_r〉 of disjoint subsets of the set of n! linear orderings on S. Given an ordering ω ∈ ∪_jA_j, we want to determine to which subset A_j the ordering ω belongs by performing a sequence of comparisons between the elements of S. The classical sorting problem corresponds to the case where the subsets A_j comprise the n! singleton sets of orderings.If a sorting problem is defined by r nonempty subsets A_j, then the information theory bound states that at least log₂r comparisons are required to solve that problem in the worst case. The purpose of this paper is to investigate the accuracy of this bound. While we show that it is usually very weak, we are nevertheless able to define a large class of problems for which this bound is good. As an application, we show that if X and Y are n element sets of real numbers, then the n² element set X + Y can be sorted with O (n²) comparisons, improving upon the n² log₂n bound established by Harper et al. The problem of sorting X + Y was posed by Berkelamp.     

Building exact computation sequences

Exact computation sequences are sequences of the form 〈L₀, A₀〉 →^S₁ 〈L₁, A₁〉 ⋯ →^S_n 〈L_n, ∅〉, where L₀ is a free algebra, A₀ is a set of conditional equations over L₀, S_i is a ‘step function’, L_i = S_i(L_i−1), and A_i = S_i(A_i−1). Each step function is the top-down reduction extesion of a set of confluent and noetherian rewrite rules. These sequences are used in solving the word problem for free algebras, since for any pair of terms t₁, t₂ ϵ L₀, t₁=_A0 t₂ iff S_n ∘ S_n−1 ∘ ⋯ ∘ S₁(t₁) = S_n ∘ S_n−1(t₂). We analyze properties of exact comput sequences such as: determining the relation between the sets 〈L_i-1, A_i−1〉 and S_i, and the output pair 〈L_i, A_i〉, and we present criteria for choosing the equations E_i in 〈L_i−1, A_i−1〉 which are used to generate the reductions S_i. We also give examples showing how to construct exact computation sequences for several axiom systems by applying the properties and the criteria presented in the article.     

Discriminative power for ensembles of linear decision rules

A novel class of ensembles of linear decision rules is introduced which includes majority voting-based ensembles as a particular case. Based on this general framework, new results are given that state the ability of a subclass to discriminate between two infinite subsets A and B in R ⁿ , thus generalizing Mazurov’s theorem for two finite sets.     

Sequencing by hybridization in few rounds

Sequencing by Hybridization (SBH) is a method for reconstructing an unknown DNA string based on obtaining, through hybridization experiments, whether certain short strings appear in the target string. Following Margaritis and Skiena (1995) [12], we study the SBH in rounds problem: The goal is to reconstruct an unknown string A (over a fixed alphabet) using queries of the form “does the string S appear in A?” for some query string S. The queries are performed in rounds, where the queries in each round depend on the answers to the queries in the previous rounds. We show that almost all strings of length n can be reconstructed in ${\log }^{1}n$ rounds with $O(n)$ queries per round. We also consider a variant of the problem in which for each substring query S, the answer is whether S appears once in the string A, appears at least twice in A, or does not appear in A. For this problem, we show that almost all strings can be reconstructed in 2 rounds of $O(n)$ queries. Our results improve the previous results of Margaritis and Skiena (1995) [12] and Frieze and Halldórsson (2002) [8].     

Restricted arc-connectivity of digraphs

Since interconnection networks are often modeled by graphs or digraphs, the edge-connectivity of a graph or arc-connectivity of a digraph are important measurements for fault tolerance of networks.The restricted edge-connectivity λ^′(G) of a graph G is the minimum cardinality over all edge-cuts S in a graph G such that there are no isolated vertices in G−S. A connected graph G is called λ^′-connected, if λ^′(G) exists.In 1988, Esfahanian and Hakimi [A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988), 195-199] have shown that each connected graph G of order n?4, except a star, is λ^′-connected and satisfies λ^′(G)?ξ(G), where ξ(G) is the minimum edge-degree of G.If D is a strongly connected digraph, then we call in this paper an arc set S a restricted arc-cut of D if D−S has a non-trivial strong component D₁ such that D−V(D₁) contains an arc. The restricted arc-connectivity λ^′(D) is the minimum cardinality over all restricted arc-cuts S.We observe that the recognition problem, whether λ^′(D) exists for a strongly connected digraph D is solvable in polynomial time. Furthermore, we present some analogous results to the above mentioned theorem of Esfahanian and Hakimi for digraphs, and we show that this theorem follows easily from one of our results.     

A note on locating eigenvalues

The numbers of the roots of det (B-λA) in different portions of the real axis are determined, whereA andB are Hermitian matrices andB is positive definite. The result is an extension of a theorem by Xiaoshu and Hua [4].     

2-Covered paths by a set of antennas with minimum power transmission range

In this paper we describe and solve the following geometric optimisation problem: given a set S of n points on the plane (antennas) and two points A and B, find the smallest radial range r∈^ℜ+ (power transmission range of the antennas) so that a path with endpoints A and B exists in which all points are within the range of at least two antennas. The solution to the problem has several applications (e.g., in the planning of safe routes). We present an O(nlogn) time solution, which is based on the second order Voronoi diagram. We also show how to obtain a path with such characteristics.     

Generateurs algebriques et systemes de paires iterantes

The notion of rational transduction is a valuable tool to compare the structures of different languages, in particular context-free languages.The explanation of this is a powerful property of rational transductions with respect to certain iterative pairs [8] and systems of iterative pairs (we define this notion in this paper), in a context-free language. (Intuitively, systems of iterative pairs describe combinations of simultaneous iterative pairs in a context-free language.)This property is the so-called Transfer Theorem, whose terms are:Let A and B be two context-free languages and let T be a rational transduction such that T(B) = A. If A has a strict system of iterative pairs σ, then B has a strict system of iterative pairs σ′, of the same type than σ.(This theorem has been proved in [8] for iterative pairs and we prove it here for systems of iterative pairs.)This theorem means that any combination of certain iterative pairs in the image language by a rational transduction must appear, in a similar way, in the source language.The main result of this paper is obtained by using the previous Transfer Theorem. This result is a characterization of context-free generators i.e. generators of the rational cone or, equivalently [10], of the full-AFL of context-free languages.     

The role of free work identity in viscous compressible flows

Some consequences of energy identity are discussed, on assumption that there exists a neighborhood of S_b of radius η where the total energy is a minimum. For fluid phase transition the neighborhood where the rest state S_b results in isolated minimum for internal energy has finite radius r that will restrict to zero as basic density ϱ_b approaches a critical value ϱ_*. Nonlinear asymptotic stability for barotropic viscous fluids is proved by use of free work identity which enables us to provide a stronger generalized energy inequality. The stability theorem is proved in a class of regular unsteady flows which are supposed to exist. Nonlinear instability for fluid phase change with zero external forces is proved. The goal is reached assuming by absurdum that ϱ is stable in L^∞ norm.     

New Structure Theorem for Subresultants

We give a new structure theorem for subresultants precising their gap structure and derive from it a new algorithm for computing them. If d is a bound on the degrees and τ a bound on the bit size of the minors extracted from Sylvester matrix, our algorithm has O(d²) arithmetic operations and size of intermediate computations 2 τ. The key idea is to precise the relations between the successive Sylvester matrix ofA and B on one hand and of A and XB on the other hand, using the notion of G-remainder that we introduce. We also compare our new algorithm with another algorithm with the same characteristics which appeared inDucos (2000).     

Numerical solution of AS + SA + Q = 0

A survey of techniques to solve A^TS + SA + Q = 0 is presented, and nine algorithms are coded and tested on a batch of examples. Which algorithm to be recommended depends mainly on the order of the system.     

A generalization of the Schützenberger product of finite monoids

For each n?1, an n-ary product ? on finite monoids is constructed. This product has the following property: Let Σ be a finite alphabet and Σ¹ the free monoid generated by Σ. For i = 1, …,n, let A_i be a recognizable subset of Σ¹, M(A_i) the syntactic monoid of A_n and M(A₁?A_n) the syntactic monoid of the concatenation product A₁?A_n. Then M(A₁?A_n)< ? (M(A₁),…,M(A_n)). The case n = 2 was studied by Schützenberger. As an application of the generalized product, I prove the theorem of Brzozowski and Knast that the dot-depth hierarchy of star-free sets is infinite.     

Solutions of nonlinear delay and advanced partial difference equations in the space lN×N1

A functional analytic method is used to prove a general theorem which establishes the existence and the uniqueness of a solution of a class of nonlinear delay and advanced partial difference equations in the Banach space l_N×N¹. The proof of the theorem has a constructive character, which enables us to obtain a bound of the solution and a region, depending on the initial conditions and the parameters of the equation under consideration, where this solution holds. Some known nonlinear partial difference equations, which appear in applications, are studied as particular cases of the theorem.     

Soft ideals and soft filters of soft ordered semigroups

It is shown that soft ordered semigroups over an ordered semigroup are actually soft ordered subsemigroups of (S,A). Soft idealistic semigroups over an ordered semigroup are soft ideals of soft ordered semigroup (S,A). The concept of soft filters of a soft ordered semigroup is introduced. It is shown that restricted complement of a soft filter is a soft prime ideal of (S,A).