Minimizing the distance to one evader while chasing another

To approach a simple game Δ² of P and E = {E₁, E₂} with no a priori evaders' role assignment and the payoff equal to the distance to one evader at an instant of catching another, we introduce a concept of casting and study the games Δ_1,2 and Δ_2,1 for preassigned and Δ_p² for open-loop casting procedures. Since Δ_p² is reduced to Δ_1,2 or Δ_2,1 which, in turn, are distinguished only by their notations, we focus attention mainly on Δ_1,2. According to the tenet of transition, Δ_1,2 is divided into a concatenation of Δ_1,2^b (basic) and Δ_1,2^a (auxiliary) games that model the problem before and after the first instant of E₁ capture. The games Δ_1,2^a, Δ_1,2^b, Δ_1,2 are studied one after another with use of the Isaacs' approach extended by Berkowitz, Breakwell, Bernhard et al.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

Complexity of Boolean algebras

We show that the elementary theory of Boolean algebras is _log-complete for the Berman complexity class _c<ω STA(*, 2^cn, n), the class of sets accepted by alternating Turing machines running in time 2^cn for some constant c and making at most n alternations on inputs of length n; thus the theory is computationally equivalent to the theory of real addition with order. We extend the completeness results to various subclasses of Boolean algebras, including the finite, free, atomic, atomless, and complete Boolean algebras. Finally we show that the theory of any finite collection of finite Boolean algebras is complete for PSPACE, while the theory of any other collection is _log-hard for _c<ω STA(*, 2^cn, n).     

New spectral lower bounds on the bisection width of graphs

The communication overhead is a major bottleneck for the execution of a process graph on a parallel computer system. In the case of two processors, the minimization of the communication can be modeled using the graph bisection problem. The spectral lower bound of λ₂|V|/4 for the bisection width of a graph is widely known. The bisection width is equal to λ₂|V|/4 iff all vertices are incident to λ₂/2 cut edges in every optimal bisection.

We present a new method of obtaining tighter lower bounds on the bisection width. This method makes use of the level structure defined by the bisection. We define some global expansion properties and we show that the spectral lower bound increases with this global expansion. Under certain conditions we obtain a lower bound depending on λ₂^β|V| with . We also present examples of graphs for which our new bounds are tight up to a constant factor. As a by-product, we derive new lower bounds for the bisection widths of 3- and 4-regular Ramanujan graphs.     

Computerized formal solutions of dynamical systems with two degrees of freedom and an application to the Contopoulos potential—II : The near-resonance case

The article describes the periodic solutions of the Contopoulos system for the case of near-resonant frequencies (ω₂² = 1 and ω = 1 − ε²² The Lindstedt method is used throughout with all the literal algebraic manipulations being computerized so that all expansions are carried to the fourth order in the small parameter ε.

It is shown that each of the two normal modes of oscillation has a bifurcation (really trifurcation) point which moves towards the origin when the exact resonance is approached, explaining why the one-to-one resonant Contopoulos system has six modes of periodic oscillations near the origin, rather then the usual number of two.

We give a single Lindstedt-type literal expansion which is valid for the three intersecting families of periodic solutions. This expansion contains two constants, A and D, representing the direct and retrograde circulations C⁺ and C⁻ when both constants are non-zero and the vertical normal mode family when A = 0.

The verifications of the analytical results by numerical integrations are also given.     

A simple solution to the l optimization problem

It is pointed out in this brief paper that the l¹ optimization problem min_{Q ε lqp¹} | H − U * Q * V |₁, H ε l_mn¹, U ε l_mq¹, V ε l_pn¹ can be solved in one step rather than two. The solution of the dual problem is obviated by the direct solution of the primal problem via linear programming. The method here is applicable to finite-dimensional problems or approximating finite-dimensional problems, in the general case.     

Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.     

Biinfinite words with maximal recurrent unbordered factors

A finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ^ωuvu^ω, where u and v are finite words, in terms of its unbordered factors.

The main result of the paper states that the words of the form ^ωuvu^ω are precisely the biinfinite words w=a₋₂a₋₁a₀a₁a₂ for which there exists a pair (l₀,r₀) of integers with l₀<r₀ such that, for every integers ll₀ and rr₀, the factor a_la_l0a_r0a_r is a bordered word.

The words of the form ^ωuvu^ω are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences “to the left” in w) of maximal length that is also a right recurrent unbordered factor of maximal length. This last result is a biinfinite analogue of a result known for infinite words.     

Thermodynamics of the cao-si02 system

In order to maintain consistency, analytical expressions for the free energy of mixing of phases should reproduce not only the phase diagrams but also the experimentally determined activities. Information on the partial molar free energies and the phase boundaries, in turn, can be used to estimate the free energy of formation of compounds.

An examination of thermochemical data in the CaO-SiO₂ system showed that ΔGδf values for -Ca₂Si0₄, which are stable at temperatures above 1710°K, are limited a maximum of 1800°K. The free energy of formation in a temperature range from about 1700 to 2400°K was estimated from the phase boundary and the activity of silica to be as follows:

2Ca0(s) + Si0₂(cristo.) = Ca2Si0₄() ΔG°f = −86303.50 − 34.338 Tjoules

An analytical expression for the free energy of mixing of the liquid phase was obtained for the entire composition range in the CaO-Si0₂ system. Confidence in the estimated G‡f for -Ca₂Si0₄ was demonstrated by good agreement of the calculated phase diagram and the experimentally determined activity of silica.     

On the latent roots of λ matrices

In this paper we consider equations defined by (1.3)–(1.2)–(1.4). We describe in detail three algorithms for the approximate determination of |λ_nr|, for |λ₁| resp. for one of the λ_j's. The single steps of the algorithms are the four fundamental operations and the positive value of k^th roots of positive numbers and the main interest of them lies in the fact that (the algorithms themselves and so) their lengths depend only on n, r and the prescribed relative error and not on the entries of the matrices A_ν.     

Behavior of the beta-splines with values of the parameters beta2 negative

In this paper we study the behavior of the beta-spline functions in the case the parameter β₂(i) is negative. We prove that a negative value exists so that if , the beta-spline functionsN_i(u) are positive. Moreover, if the control vertices are such that x₀ x_m−1, we have proved that the design curve keeps the properties already proved in the case β₂(i) 0.     

1-Inverses for polynomial matrices of non-constant rank

Let p₁, … p_t be polynomials in ⁿ with a variety V of common zeros contained in a suitable open set U. Explicit formulas are provided to construct rational functions λ₁, … λ_s such that Σ_i=1^sp_iλ_i 1, and such that the singularities of the λ_i are contained in U. This result is applied to compute rational functions-valued 1-inverses of matrices with polynomial coefficients, which do not have constant rank, while retaining control over the location of the singularities of the rational functions themselves.     

Bias associated with the discriminant analysis approach to the estimation of mixing proportions

The estimation of the mixing proportion π₁, in which the first of two multivariate normal groups occur is considered on the basis of a sample drawn from a mixture of them. Under the model studied, there are also data of known origin available from each of the groups for the formation of a discriminant rule R. The bias of the estimator of π₁, based on the proportion of the mixture data assigned to the first group by R, is investigated. Also, the case where the data of known origin are taken to be correlated is considered.     

Fast evaluation of radial basis functions: I

This paper describes some new techniques for the rapid evaluation and fitting of radial basic functions. The techniques are based on the hierarchical and multipole expansions recently introduced by several authors for the calculation of many-body potentials. Consider in particular the N term thin-plate spline, s(x) = Σ_j=1^N d_jφ(x−x_j), where φ(u) = |u|²log|u|, in 2-dimensions. The direct evaluation of s at a single extra point requires an extra O(N) operations. This paper shows that, with judicious use of series expansions, the incremental cost of evaluating s(x) to within precision ε, can be cut to O(1+|log ε|) operations. In particular, if A is the interpolation matrix, a_i,j = φ(x_i−x_j, the technique allows computation of the matrix-vector product Ad in O(N), rather than the previously required O(N²) operations, and using only O(N) storage. Fast, storage-efficient, computation of this matrix-vector product makes pre-conditioned conjugate-gradient methods very attractive as solvers of the interpolation equations, Ad = y, when N is large.     

Gas-sensing property and mechanism of CaxLa1−xFeO3 ceramics

LaFEO₃ and Ca_xLa_1−xFeO₃ ceramic powders have been prepared by the coprecipitation method from La(NO₃)₃, Fe(NO₃)₃ and Ca(NO₃)₂ aqueous solutions. The orthorhombic perovskite phases of LaFeO₃ and Ca_xLa_1−xFeO₃ are characterized by X-ray diffraction patterns. The sensors fabricated with those powders have high sensitivity to alcohol. Partial substitution of La³⁺ in LaFeO₃ with Ca²⁺ can enhance the sensitivity of the materials to reducing gases. The resistance of an LaFeO₃ sensor in air, vacuum and alcohol-containing air has been measured. Complex impedance spectroscopy has been used to try and analyse the gas-sensing mechanism. According to the experimental results, it can be deduced that the surface adsorptive and lattice oxygen govern the sensing properties of LaFeO₃ and Ca_xLa_1−xFeO₃ ceramics.     

Trace detection of nitroaromatic compounds with layer-by-layer assembled {SBA/PSS}n/PDDA modified electrode

The {SBA/PSS}_n/PDDA films modified electrode was prepared by layer-by-layer (LBL) assembly with mesoporous SiO₂ (SBA), poly(sodium 4-styrene-sulfonate) (PSS) and poly(diallyldimethylammonium chloride) (PDDA) in this paper. SBA is a large pore-size mesoporous material with highly ordered hexagonally arranged mesochannels and high thermal stability etc. The electrochemical characteristics of the {SBA/PSS}_n/PDDA films have been studied by electrochemical impedance spectroscopy in 0.1 M KCl solution containing 5.0 mM Fe(CN)₆³⁻/Fe(CN)₆⁴⁻ at the formal potential of 0.230 V. The ultratrace nitroaromatic compounds (NACs) such as TNT, TNB, DNT and DNB were determined by differential pulse voltammetry (DPV) measurement. The sensitivities for NACs determination with {SBA/PSS}_n/PDDA modified electrode were dependent on the number of layers, pH and ionic strength of electrolyte, based on which a set of optimized conditions for film fabrication was inferred. The current responses were linear with NACs ranging from 10⁻⁹ to 10⁻⁷ mol/l. The results showed that the {SBA/PSS}_n/PDDA modified electrode established a new way for fast, simple and sensitive analysis of NACs.     

On the type of a polynomial f, when f(0)f−f(0)f is a monomial

A polynomial is said to be of type (p₁, p₂, p₃) relative to a directed line in the complex plane if, counting multiplicities, it has p₁ zeros to the left of, p₂ zeros on, and p₃ zeros to the right of the line. In this paper we determine explicitly the types of all polynomials belonging to a very restricted (but infinite) family of polynomials. A polynomial ƒ belongs to this family if and only if its coefficients are such that the polynomial ƒ^*(0)ƒ(z)−ƒ(0) ƒ^*(z) is a monomial; here ƒ^* denotes the reflection of ƒ in the directed line.

A special case of the present result appeared in an earlier publication.     

Experimental numerical studies on a supercomputer of natural convection in an enclosure with localized heating

We present particle simulations of natural convection of a symmetrical, nonlinear, three-dimensional cavity flow problem. Qualitative studies are made in an enclosure with localized heating. The assumption is that particles interact locally by means of a compensating Lennard-Jones type force F, whose magnitude is given by −G/r^p + H/r^q.

In this formula, the parameters G, H, p, q depend upon the nature of the interacting particles and r is the distance between two particles. We also consider the system to be under the influence of gravity. Assuming that there are n particles, the equations relating position, velocity and acceleration at time t_k = kΔt, K = 0, 1, 2, …, are solved simultaneously using the “leap-frog” formulas. The basic formulas relating force and acceleration are Newton's dynamical equations F_i,k = m_ia_i,k, I = 1, 2, 3, …, n, where m_i is the mass of the ith particle.

Extensive and varied computations on a CRAY X - MP/24 are described and discussed, and comparisons are made with the results of others.     

On the power of alternation on reversal-bounded alternating Turing machines with a restriction

Whether or not there is a difference of the power among alternating Turing machines with a bounded number of alternations is one of the most important problems in the field of computer science. This paper presents the following result: Let R(n) be a space and reversal constructible function. Then, for any k 1, we obtain that the class of languages accepted by off-line 1-tape rσ_k machines running in reversal O(R(n)) is equal to the class of languages accepted by off-line 1-tape σ₁ machines running in reversal O(R(n)). An off-line 1-tape σ_k machine M is called an off-line 1-tape rσ_k machine if M always limits the non-blank part of the work-tape to at most O(R(n) log n) when making an alternation between universal and existential states during the computation.