A second step toward the strong polynomial-time hierarchy

In this paper we discuss the concepts ofimmunity andsimplicity in levels of the relativized Polynomial-time Hierarchy just aboveP. We consider various diagonalization techniques with which oracle sets can be constructed relative to which strong separations between language classes in the first two levels of this hierarchy are established. In particular, we build oracle sets for separation of relativized Σ ₂ ^P from relativizedNP with immunity, of relativized Σ ₂ ^P from relativizedNP with bi-immunity, of relativized Σ ₂ ^P from relativized Δ ₂ ^P with immunity, of relativized Π ₂ ^P from relativized Δ ₂ ^P with immunity, and finally of relativized Σ ₂ ^P from relativized Π ₂ ^P with simplicity.     

Thermodynamic assessment of the KCl–K2CO3–NaCl–Na2CO3 system

Phase equilibria and thermodynamic properties of the KCl–K₂CO₃–NaCl–Na₂CO₃ system were analyzed on the basis of the thermodynamic evaluation of the KCl–NaCl,KCl–K₂CO₃,NaCl–Na₂CO₃,K₂CO₃–Na₂CO₃ and KCl–K₂CO₃–NaCl–Na₂CO₃ systems. The Gibbs energies of individual phases was approximated by two-sublattice models for ionic liquids and crystals. Most of the experimental information was well described by the present set of thermodynamic parameters. The lowest monovariant eutectic temperature in the KCl–NaCl–Na₂CO₃ system is located at 573 ^°C, with a composition of X_Na2CO3=0.31,X_KCl=0.35 and X_NaCl=0.34.     

An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

Coincidental extension of scattered context languages

For a symbol, #, and a string, x = a ₁ a ₂ ...a _{n - 1} a _n , any string of the form # ⁱ a ₁ # ⁱ a ₂ # ⁱ...# ⁱ a _{n - 1} # ⁱ a _n # ⁱ, where 0, is a coincidental #-extension of x. A language, K, is a coincidental #-extension of L if every string of K represents a coincidental extension of a string in L and the deletion of all #s in K results in L. This paper proves that for every recursively enumerable language, E, there exists a propagating scattered context language that represents a coincidental extension of E. Received: 31 October 2001 / 31 January 2003     

Monotone properties of certain classes of solutions of second-order difference equations

The authors consider the difference equations

δ(a_nδx_n)=q_nx_n+1

and

δ(a_nδx_n)=q_nf(x_n+1),

where a_n > 0, q_n > 0, and f: R å R is continuous with uf(u) > 0 for u ≠ 0. They obtain necessary and sufficient conditions for the asymptotic behavior of certain types of nonoscillatory solutions of (*) and sufficient conditions for the asymptotic behavior of certain types of nonoscillatory solutions of (**). Sufficient conditions for the existence of these types of nonoscillatory solutions are also presented. Some examples illustrating the results and suggestions for further research are included.     

Electrochemical DNA biosensor for the detection of interaction between di[azino-di(5,6-azafluorene)-κ-NN′]dichlormanganous and DNA

A new Mn(II) complex of MnL₂Cl₂ (L = azino-di(5,6-azafluorene)-κ²-NN′) was synthesized and utilized as an electrochemical indicator for the determination of hepatitis B virus (HBV) based on its interaction with MnL₂Cl₂. The electrochemical behavior of interaction of MnL₂Cl₂ with salmon sperm DNA was investigated on glassy carbon electrode (GCE). In the presence of salmon sperm DNA, the peak current of [MnL₂]²⁺ was decreased and the peak potential was shifted positively without appearance of new peaks. The binding ratio between [MnL₂]²⁺ and salmon sperm DNA was calculated to be 2:1 and the binding constant was 3.72 × 10⁸ mol² L⁻². The extent of hybridization was evaluated on the basis of the difference between signals of [MnL₂]²⁺ with probe DNA before and after hybridization with complementary sequence. Control experiments performed with non-complementary and mismatch sequence demonstrated the good selectivity of the biosensor. With this approach, a sequence of the HBV could be quantified over the range from 1.76 × 10⁻⁸ to 1.07 × 10⁻⁶ mol L⁻¹, with a linear correlation of r = 0.9904 and a detection limit of 6.80 × 10⁻⁹ mol L⁻¹. Additionally, the binding mechanism was preliminarily discussed. The mode of interaction between MnL₂Cl₂ and DNA was found to be primary intercalation binding.     

On Space Efficient Two Dimensional Range Minimum Data Structures

The two dimensional range minimum query problem is to preprocess a static m by n matrix (two dimensional array) A of size N=m⋅n, such that subsequent queries, asking for the position of the minimum element in a rectangular range within A, can be answered efficiently. We study the trade-off between the space and query time of the problem. We show that every algorithm enabled to access A during the query and using a data structure of size O(N/c) bits requires Ω(c) query time, for any c where 1≤c≤N. This lower bound holds for arrays of any dimension. In particular, for the one dimensional version of the problem, the lower bound is tight up to a constant factor. In two dimensions, we complement the lower bound with an indexing data structure of size O(N/c) bits which can be preprocessed in O(N) time to support O(clog ² c) query time. For c=O(1), this is the first O(1) query time algorithm using a data structure of optimal size O(N) bits. For the case where queries can not probe A, we give a data structure of size O(N⋅min {m,log n}) bits with O(1) query time, assuming m≤n. This leaves a gap to the space lower bound of Ω(Nlog m) bits for this version of the problem.     

A class of hybrid collocation methods for third-order ordinary differential equations

A class of numerical methods is proposed for solving general third-order ordinary differential equations directly by collocation at the grid points x = x _n+j , i = 0(1)k and at an off grid point x = x _n+u , where k is the step number of the method and u is an arbitrary rational number in (x _n , x _n+k ). A predictor of order 2k ? 1 is also proposed to cater for y _n+k in the main method. Taylor series expansion is employed for the calculation of y _n+1, y _n+2, y _n+u and their higher derivatives. Evaluation of the resulting method at x = x _n+k for any value of u in the specified open interval yields a particular discrete scheme as a special case of the method. The efficiency of the method is tested on some general initial value problems of third-order ordinary differential equations.     

Fast Constructive Recognition of a Black Box Group Isomorphic toSnorAnusing Goldbach’s Conjecture

The well-known Goldbach Conjecture (GC) states that any sufficiently large even number can be represented as a sum of two odd primes. Although not yet demonstrated, it has been checked for integers up to 10¹⁴. Using two stronger versions of the conjecture, we offer a simple and fast method for recognition of a gray box group G known to be isomorphic to S_n(or A_n) with knownn ≥  20, i.e. for construction1of an isomorphism from G toS_n (or A_n). Correctness and rigorous worst case complexity estimates rely heavily on the conjectures, and yield times of O([ρ + ν + μ ] n log²n) or O([ ρ + ν + μ ] n logn / loglog n) depending on which of the stronger versions of the GC is assumed to hold. Here,ρ is the complexity of generating a uniform random element of G, ν is the complexity of finding the order of a group element in G, and μ is the time necessary for group multiplication in G. Rigorous lower bound and probabilistic approach to the time complexity of the algorithm are discussed in the Appendix.     

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.     

Proper Learning Algorithm for Functions of k Terms under Smooth Distributions

In this paper, we introduce a probabilistic distribution, called a smooth distribution, which is a generalization of variants of the uniform distribution such as q-bounded distribution and product distribution. Then, we give an algorithm that, under the smooth distribution, properly learns the class of functions of k terms given as _k ^k_n={g(f₁(v), …, f_k(v)) | g _k, f₁, …, f_{k n}} in polynomial time for constant k, where _k is the class of all Boolean functions of k variables and _n is the class of terms over n variables. Although class _k ^k_n was shown by Blum and Singh to be learned using DNF as the hypothesis class, it has remained open whether it is properly learnable under a distribution-free setting.     

Influence of tyre pressure and vertical load on coefficient of rolling resistance and simulated cycling performance

The coefficient of rolling resistance (C _r) for pneumatic tyres is dependent on hysteresis loss from tyre deformation which is affected by the vertical force applied to the tyres (F _v) and the tyre inflation pressure (P _r). The purpose of this paper was to determine the relative influence of five different levels of P _r and four different levels of F _v on C _r and to examine the relationships of C _r with P _r and F _v during cycling locomotion. F _v was modified through carriage of additional mass by the subject. C _r was determined with the coasting deceleration method from measurements performed in a level hallway. Iterations minimizing the sum of the squared difference between the actual deceleration distance and a predicted deceleration distance were used to determine C _r. This latter distance was computed from a derivation based on Newton's second law applied to the forces opposing motion. C _r was described by a hyperbolic function of P _r (C _r = 0.1071 P _r ^?0.477, r ² = 0.99, p &lt; 0.05), decreasing 62.4% from 150 kPa (C_r= 0.0101) to 1200 kPa (C_r = 0.0038). F _v was related to C _r by a polynomial function (C _r = 1.92.10^?8 F _v ² ?2.86.10^?5 F _v + 0.0142, r ² = 0.99, p = 0.084), with an added mass of 15 kg (C _r = 0.0040) resulting in an 11.4% increase in C _r compared with no added mass (C _r = 0.0035). From this study, it is concluded that the relationships of P _r and F _v with C _r for cycling are non-linear. Furthermore, a simulation model shows that changes in P _r and F _v of the magnitude examined here have an important effect on competitive cycling performance.     

Actions,finite state sets and applications to trees

Let M be a monoid acting on a set X; for any x?X and A?X we put x ^?1 A = {m?M/xm?A}. Call A?X finite state if card {x ^?1 A/x?X} <∞.

The finite state subsets of T _Σvia the action T _Σ × P _Σ→T _Σare the recognizable forests (P _Σis the monoid of all Σ-trees with just one leaf labeled by a variable x).

Next we prove that the recognizability of forests is equivalent to the finiteness of a certain “syntactic” monoid A Mezei's-like theorem for trees is established: the finite state subsets of T _Σ × T_г are exactly the finite unions of sets of sets of the form B × C B?Rec(T _Σ) and C?Rec(T _г) Another characterization of such relations is given using bimorphisms.     

Perfect r-domination in the Kronecker product of two cycles, with an application to diagonal/toroidal mesh

If r?1, and m and n are each a multiple of (r+1)²+r², then each isomorphic component of C_m×C_n admits of a vertex partition into (r+1)²+r² perfect r-dominating sets. The result induces a dense packing of C_m×C_n by means of vertex-disjoint subgraphs, each isomorphic to a diagonal array. Areas of applications include efficient resource placement in a diagonal mesh and error-correcting codes.     

Effect of Porosity on free and forced vibration characteristics of the GPL reinforcement composite nanostructures

This article investigates the influence of porosity on free and forced vibration characteristics of a nanoshell reinforced by graphene platelets (GPL). The material properties of piece-wise graphene-reinforced composites (GPLRCs) are assumed to be graded in the thickness direction of a cylindrical nanoshell and estimated using a nanomechanical model. In addition, because of imperfection of the current structure, three kinds of porosity distributions are considered. The nanostructure is modeled using modified strain gradient theory (MSGT) which is a size-dependent theory with three length scale parameters. The novelty of the current study is to consider the effects of porosity, GPLRC and MSGT on dynamic and static behaviors of the nanostructure. Considering three length scale parameters ( $l_0=5h$, $l_1=3h$, $l_2=5h$ ) in MSGT leads to a better agreement with MD simulation in comparison by other theories. Finally, effects of different factors on static and dynamic behaviors of the porous nanostructure are examined in detail.     

A variable-precision square root implementation for field programmable gate arrays

Applications requiring variable-precision arithmetic often rely on software implementations because custom hardware is either unavailable or too costly to build. By using the flexibility of the Xilinx XC4010 field programmable gate arrays, we present a hardware implementation of square root that is easily tailored to any desired precision. Our design consists of three types of modules: a control logic module, a data path module to extend the precision in 4-bit increments, and an interface module to span multiple chips. Our data path design avoids the common problem of large fan-out delay in the critical path. Cycle time is independent of precision, and operation latency can be independent of interchip communication delays.Notation S_j square root digit of weight 2^–j - S _j {–1, 0, 1} - S[j] computed square root value as of stepj - S _j ^s sign bit in the representation ofS _j in sign and magnitude form - S _j ^m magnitude bit in the representation ofS _j in sign and magnitude form - w[j] residual at stepj in two's complement carry-save representation - a sum vector in the carry-save representation of 2w[j] - b carry vector in the carry-save representation of 2w[j] - a _i bit of weight 2^–i in the sum vector,a - b_i bit of weight 2^–i in the carry vector,b - T[j]=–S[j – 1]s_j – s _j ² 2^–(j+1) T _i bit of weight 2^–i inT     

Rational Solutions of Riccati-like Partial Differential Equations

When factoring linear partial differential systems with a finite-dimensional solution space or analysing symmetries of nonlinear ODEs, we need to look for rational solutions of certain nonlinear PDEs. The nonlinear PDEs are called Riccati-like because they arise in a similar way as Riccati ODEs. In this paper we describe the structure of rational solutions of a Riccati-like system, and an algorithm for computing them. The algorithm is also applicable to finding all rational solutions of Lie’s system { ∂_xu + u² + a₁u + a₂v + a₃, ∂_yu + uv + b₁u + b₂v + b₃, ∂_xv + uv + c₁u + c₂v + c₃, ∂_yv + v² + d₁u + d₂v + d₃},where a₁, . . . , d₃are rational functions of x and y.     

Mason: morphological simplification

The traditional rounding and filleting morphological filters are biased. Hence, as r grows, the rounding R_r (S) of S shrinks and the filleting F_r (S) grows. A shape S is r-regular when R_r (S) = F_r (S) = S. The combinations F_r (R_r (S)) and R_r (F_r (S)) produce nearly r-regular shapes, but retain a bias: F_r (R_r (S)) is usually smaller than S and R_r (F_r (S)) is larger. To overcome this bias, we propose a new filter, called Mason. The r-mortar M_r (S) of S is F_r (S)–R_r (S), and the stability of a point P with respect to S is the smallest value of r for which P belongs to M_r (S). Stability provides important information about the shape’s imbedding that cannot be obtained through traditional topological or differential analysis tools. F_r (R_r (S)) and R_r (F_r (S)) only affect space in M_r (S). For each maximally connected component of M_r (S), Mason performs either F_r (R_r (S)) or R_r (F_r (S)), choosing the combination that alters the smallest portion of that component. Hence, Mason acts symmetrically on the shape and on its complement. Its output is guaranteed to have a smaller symmetric difference with the original shape than that of either combination F_r (R_r (S)) or R_r (F_r (S)). Many previously proposed shape simplification algorithms were focused on reducing the combinatorial storage or processing costs of a shape at the expense of the smoothness and regularity or altered the shape in regular portions that did not exhibit any high frequency complexity. Mason is the first shape simplification operator that is independent of the particular representation and offers the advantage of preserving portions of the boundary of S that are regular at the desired scale.