The complexity of a multiprocessor task assignment problem without deadlines

We construct a sequence of monotone Boolean functions h_n :{0, 1}ⁿ→{0, 1}ⁿ, such that the monotone complexity of h_n is of order $\text{n}{}^2\text{log n}$. This result includes the largest known lower bound of this kind. Previously there were an $\text{Ω(n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{)}$ bound for the Boolean matrix product, an $\text{Ω(n}{}^{\mathrm{<mtext>5</mtext><mtext>3</mtext>}}\text{)}$ bound for Boolean sums and an $\text{Ω(}\text{n}{}^2\text{log}{}^2\text{n}\text{)}$ bound by the author for the same functions h_n. This new lower bound is proved by new methods which probably will turn out to be useful also for other problems.     

On nonstochastic languages and homomorphic images of stochastic languages

Using a simple method we find some nonstochastic and stochastic languages related to the Dyck sets and to the languages $\text{{wcw¦w in {a, b}}{}^1\text{}}$ and $\text{{wcw}{}^{\mathrm{R}}\text{¦w in {a, b}}{}^1\text{}}$. Using the theory of uniformly distributed sequences, we present a sufficient condition for a one-letter language to be nonstochastic. Among the applications is the result that {a^p¦p is a prime} is nonstochastic. We also study the images of stochastic and rational stochastic languages under nonerasing and arbitrary homomorphisms as well as their relations to some well-known families. Finally, we introduce a large class of bounded languages and show that it is contained in /of_∩ (DUP) = the smallest intersection-closed AFL containing $\text{DUP}\text{= {a}{}^{\mathrm{n}}\text{b}{}^{\mathrm{n}}\text{¦n in N}}$, which is a subfamily of /oK(/oL_Q = the image of the family of rational stochastic languages under nonerasing homomorphisms.     

Asymptotic properties of minimax trees and game-searching procedures

The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods.If the terminal positions are assigned a WIN-LOSS status with the probabilities P₀ and 1 ? P₀, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P₀ is higher or lower than some fixed-point probability $\text{P1(d)}$. When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value $\text{v1}$, which is the $\text{(1 ? P1)-}\text{fractile}$ of the terminal distribution.Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions if positions if $\text{P}{}_0\text{≠ P1}$ and $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions if $\text{P}{}_0\text{= P1}$, the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure.     

Laser-induced marine bioluminescence measurements and the potential for airborne remote sensing

Bioluminescence in cultures of the dinoflagellate Pyrocystis lunula at various temperatures were stimulated using a pulsed dye laser and Rhodamine 6G dye having an optimum lasing wavelength of $\text{586 ± 30}\text{nm}$. Following an intense “first flash” response, the flash intensity decayed in logarithmic fashion with successive laser shots. Samples pulsed to exhaustion were found to completely recover during the 12 h photophase. The total stimulable light (TSL) was calculated to be between $\text{4.5 × 10}{}^{\mathrm{?10}}$ J cell^?1 and $\text{38.5 × 10}{}^{\mathrm{?10}}$ J cell^?1. The time from stimulation to maximum light emission ($\text{t}{}_{\mathrm{m}}$) was found to vary with temperature logarithmically from approximately 11°C to 28°C. The corresponding regression equation was found to predict temperatures to within ±0.4°C. These results provide the basis for predicting the feasibility of an airborne laser transceiver for mapping the distribution of ocean bioluminescence. The potential exists for determining ocean surface/near surface temperature from measurements of the response pulse time parameters.     

Some polynomials that are hard to compute

Using the result of Heintz and Sieveking [1], we show that the polynomials $\text{Σ}{}_{\mathrm{1?j?d}}\text{b}{}^{\mathrm{<mtext>1</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{j}}$ with b positive real different from one, and Σ_1?j?dj^rX^j with r rational not integer, are hard to compute.     

On some bounded semiAFLs and AFLs

Goldstine [8] has conjectured that not all context-free languages are contained in $\text{F}$_∩($\text{B}$)—the smallest AFL closed under intersection and containing all bounded languages. We prove this by showing that the linear context-free language pal is not in $\text{F}$_∩($\text{B}$). Inclusion relations among various subfamilies of $\text{F}$∩($\text{B}$) as well as their closure properties are studied. It is shown that all languages defined by polynomials whose coefficients are natural numbers are in $\text{M}$_∩(prod)—the smallest intersection-closed semiAFL containing the language $\text{prod}\text{=a}{}^{\mathrm{m}}\text{b}{}^{\mathrm{n}}\text{c}{}^{\mathrm{mn}}\text{s|m,n in N}$. This implies that the corresponding full semiAFL$\text{M}\text{?}$_∩ (prod) is equal to the smallest intersection-closed full semiAFL containing all recursively enumerable bounded languages. An analogous result for all bounded languages is also obtained. Since pal is not in$\text{M}\text{?}$_∩(prod), it follows that $\text{M}\text{?}$^lin_∩(prod) is a semiAFL closed under intersection and linear-erasing homomorphism but is not closed under Kleene⁺, homomorphism, or nonerasing homomorphic replication. This solves a problem considered by Book and Greibach [2]. Finally, nonprincipality of some semiAFLs and AFLs is established. As a consequence, we solve a problem of Ginsburg [6].     

A note on redundant Disk Modulo allocation

Preliminary consideration of redundant Disk Modulo file allocations to multiple disks finds that strict optimal performance can be obtained for 2^p disks via $\text{(?}\text{p}{}^{\mathrm{<mtext>p</mtext>}}\text{2}\text{?)}$-fold replication.     

Lower bounds for polynomials with algebraic coefficients

We give a method, based on algebraic geometry, to show lower bounds for the complexity of polynomials with algebraic coefficients. Typical examples are polynomials with coefficients which are roots of unity, such as

$\text{Σ}\text{j=1}\text{d}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{i}}$

and

$\text{Σ}\text{j=i}\text{d}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>pi</mtext>}}\text{X}{}^{\mathrm{j}}$

where p_j is the jth prime number.We apply the method also to systems of linear equations.     

Three symmetric solutions of lidstone boundary value problems for difference and partial difference equations

We consider the boundary value problem $\text{δ}{}^{\mathrm{2m}}\text{y(k-m)=f(y(k),δ}{}^2\text{y(k-1),…,δ}{}^{\mathrm{2i}}\text{y(k-1),…,δ}{}^{\mathrm{2(m-1)}}\text{y(k-(m-1)))}\text{kϵ{a+1,…,b+1},}\text{δ}{}^{\mathrm{2i}}\text{y(a+1-m)=δ}{}^{\mathrm{2i}}\text{y(b+1+m-2i)=0,}\text{0≤i≤m-1,}$ where m ≥ 1 and (−1)^m f R^m → [0, ∞) is continuous. By using Amann and Leggett-Williams' fixed-point theorems, we develop growth conditions on f so that the boundary value problem has triple positive symmetric solutions. The results obtained are then applied in the investigation of radial solutions for certain partial difference equation subject to Lidstone type conditions.     

Time optimal control of a second order system with hydraulic fluidic implementation

This study was undertaken to determine the requirements for fluidic implementation of a time optimal “target acquisition” control system. Analytic expressions for the optimal control function $\text{u}{}^1$, the systems trajectory curve, switch curve and minimum transition time are determined for a given plant. The optimal control $\text{u}{}^1$ is obtained as a function of the system state variables $\text{u}{}^1\text{[x(t)]}$ so that $\text{u}{}^1$ is generated in a feedback sense. The component requirements for hydraulic fluidic implementation of this minimum time control system are stringent. Therefore, linear proportional and sub-optimal control systems are also considered. The decision to use optimal, sub-optimal or proportional control requires, among other things, weighing the advantages of high performance against the complexity of the control circuit. In this case the sub-optimal control appears to be the best choice because it requires simple control circuitry and its transition time is nearly optimal. The use of this type of control eliminates the need for a number of components required in the optimal system.     

Uniform computational complexity of the derivatives of C∞-functions

We discuss the uniform computational complexity of the derivatives of C^∞-functions in the model of Ko and Friedman (Ko, Complexity Theory of Real Functions, Birkhäuser, Basel, 1991; Ko, Friedman, Theor. Comput. Sci. 20 (1982) 323–352). We construct a polynomial time computable real function g∈C^∞[−1,1] such that the sequence $\text{{|g}{}^{\mathrm{(n)}}\text{(0)|}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is not bounded by any recursive function. On the other hand, we show that if f∈C^∞[−1,1] is polynomial time computable and the sequence of the derivatives of f is uniformly polynomially bounded, i.e., |f⁽ⁿ⁾(x)| is bounded by 2^p(n) for all x∈[−1,1] for some polynomial p, then the sequence $\text{{f}{}^{\mathrm{(n)}}\text{}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is uniformly polynomial time computable.     

Selection and sorting with limited storage

When selecting from, or sorting, a file stored on a read-only tape and the internal storage is rather limited, several passes of the input tape may be required. We study the relation between the amount of internal storage available and the number of passes required to select the Kth highest of N inputs. We show, for example, that to find the median in two passes requires at least $\text{ω(N}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ and at most $\text{O(N}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{log N)}$ internal storage. For probabilistic methods, $\text{θ(N}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ internal storage is necessary and sufficient for a single pass method which finds the median with arbitrarily high probability.     

Nonsimilar boundary layers on the leeside of cones at incidence

It is known that the similarity equations for the leeward line of symmetry of a cone have no solutions for $\text{?1 < k}{}_2{}^1\text{< k < k}{}_1\text{1 < 0}$, where k is the incidence parameter of Moore, and $\text{k}{}_1{}^1\text{, k}{}_2{}^1$ depend on the external Mach number and enthalpy ratio. In this paper we present evidence that a leeside integration for such k terminates at a finite distance from the vertex in a singularity of the type analyzed by Stewartson and Simpson for entry flow in a curved pipe, and compare the theory with a representative numerical solution at $\text{k = ?}\text{1}\text{2}$. A possible interpretation of this singularity is that the boundary layers growing from the windward line of symmetry have collided, and support for this view is given by windward to leeward integrations for a range of values of k. For k such that the similarity equations have solutions, these are interpreted as limits of more general solutions.     

Some remarks on a conjecture in parameter adaptive control

A.S. Morse has raised the following question: Do there exist differentiable functions

$\text{f:R}{}^2\text{→ R}\text{and}\text{g:R}{}^2\text{→ R}$

with the property that for every nonzero real number λ and every (x₀, y₀) ∈ $\text{R}$² the solution (x(t),y(t)) of

$\text{x}\text{?}\text{(t) = x(t) + λf(x(t),y(t))}$

,

$\text{y}\text{?}\text{(t) = g(x(t),y(t))}$

,

$\text{x(0) = x}{}_0\text{, y(0) = y}{}_0$

, is defined for all t ? 0 and satisfies

$\text{lim}\text{t → + ∞}$

and y(t) is bounded on [0,∞)? We prove that the answer is yes, and we give explicit real analytic functions f and g which work. However, we prove that if f and g are restricted to be rational functions, the answer is no.     

Insertion languages

The operations of insertion ( ← ) and iterated insertion ( ←₁ ) are simple variants of Kleene's operations · and 1 [15] in a manner similar to the operations shuffle and iterated shuffle (see e.g. [13, 23, 20, 14]). Using the operation of iterated insertion, we can generate both the semi-Dyck and the two-sided Dyck languages from certain finite subsets of these languages. Thus the class of languages of the form $\text{S}{}^{\mathrm{\leftarrow }}{}^1$ for finite S forms a natural class of generalized Dyck languages. This class is equivalent to the class of pure unitary languages discussed in [6]. We investigate this class further, by examining for it the problems of equivalence, ambiguity, and determinism, all of which are easily decidable. On the other hand, we show that the problem “$\text{S}{}^{\mathrm{\leftarrow }}\text{1 ∩ T}{}^{\mathrm{\leftarrow }}\text{1 = {λ}?}$” is undecidable for finite, unambiguous S and T. Furthermore, by extending the regular expressions to include the operations ← and $\text{←}{}_1$, we obtain the class of insertion languages which generalizes both the regular languages and the Dyck languages, but is properly contained within the class of context-free languages. Our main result here is that the problem “$\text{L = ∑}{}^1\text{?}$” is undecidable for the class of insertion languages. From this result, it follows that the equivalence problem and the problem “IsL regular?” are also undecidable for this class.     

Physical parallel devices are not much faster than sequential ones

It is proven that any (uniform) family of physical parallel devices, recognizing a language C? with time-complixity T_P(n), can be simulated by a (uniform) family of sequential devices with time-complexity $\text{T}{}_{\mathrm{P}}\text{(n)}{}^{\mathrm{<mtext>1</mtext><mtext>d</mtext>}}$ (d is a constant, depending on the technology, but not greater than 13).     

Stresses around two equal circular elastic inclusions in a pressurised cylindrical shell

The stress problem of two equal circular elastic inclusions in a pressurised cylindrical shell has been solved by using single inclusion solutions together with Graf's addition theorem. The effect of the inter-inclusion distance on the interface stresses in the shell as well as in the inclusion is studied. The results obtained for small values of curvature parameter β $\text{(β}{}^2\text{= (a}{}^2\text{/8Rt) [12(1?ν}{}^2\text{)]}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{, a, R, t}$ being inclusion radius and shell radius and thickness) when compared with the flat-plate results show good agreement. The results obtained in non-dimensional form are presented graphically.     

Compatibility condition and existence results in discrete finite incompressible elasticity

A theory on the existence of solutions of the discretized equilibrium equations in incompressible finite elasticity is given. A compatibility condition between the space of displacements and the space of pressures is introduced and is studied in a particular case of finite element spaces, using $\text{Q}{}^1$ and $\text{Q}{}^0$ isoparametric elements. An original assembling of these elements is presented which leads to discrete spaces satisfying the compatibility condition.