Finite Derivation Type Implies The Homological Finiteness Condition FP3

A monoid M that admits a finite convergent presentation satisfies the homological finiteness condition FP∞ and Squier's combinatorial property of having finite derivation type. Although Squier has given an example of a finitely presented monoid S₁ that satisfies the condition FP∞, but that does not have finite derivation type, the exact relationship between these two conditions is unsolved. Here we establish a partial result by showing that for finitely presented monoids the property of having finite derivation type implies the homological finiteness conditions FP₃ . Hence, the property FP₃ is strictly weaker than the property of having finite derivation type.     

On properties not inherited by monoids from their Schützenberger groups

We give an example of a monoid with finitely many left and right ideals, all of whose Schützenberger groups are presentable by finite complete rewriting systems, and so each have finite derivation type, but such that the monoid itself does not have finite derivation type, and therefore does not admit a presentation by a finite complete rewriting system. The example also serves as a counterexample to several other natural questions regarding complete rewriting systems and finite derivation type. Specifically it allows us to construct two finitely generated monoids M and N with isometric Cayley graphs, where N has finite derivation type (respectively, admits a presentation by a finite complete rewriting system) but M does not. This contrasts with the case of finitely generated groups for which finite derivation type is known to be a quasi-isometry invariant. The same example is also used to show that neither of these two properties is preserved under finite Green index extensions.     

Pseudo-natural algorithms for finitely generated presentations of monoids and groups

Let G be a finitely generated group such that the word problem for G is E_n-decidable for some n≥1. Then there exists a finitely generated context-sensitive presentation of G such that the word problem for this presentation can be solved by a pseudo-natural algorithm in the class E_n. This result cannot be strengthened to always yield a context-free presentation. However, it can be extended to hold for finitely generated monoids as well.     

Optimal utilization of fixed-capacity channels in feedback control

The performance limitations on the linear control of a linear plant, due to the presence of a feedback channel with finite information capacity, are considered in this paper. This situation may arise in such diverse applications as (a) the remote control of a plant, using a digital data link for feedback, (b) where quantization errors and bit errors of a digital controller may be modelled as occurring in a noisy digital channel in cascade with an ideal controller, and (c) in human-operator modelling, where the sensory feedback channels are characterized by fixed information capacity due to neural noise. The principle result obtained is that, given the state-dimension n of the plant and the channel capacity ?, reliability function E(R), and block encoding time $\text{T> >}\text{1}\text{C}$, the optimum data-rate R satisfies the equation 2R=nE(R). This rate provides the optimum tradeoff between the effects of quantization errors and message errors. It is seen that R_opt→C as n becomes large, but that good channel performance is retained provided that $\text{> >}\text{n}\text{T}$.     

One way finite visit automata

A one-way preset Turing machine with base L is a nondeterministic on-line Turing machine with one working tape preset to a member of L. FINITEREVERSAL($\text{L}$) (FINITEVISIT ($\text{L}$)) is the class of languages accepted by one-way preset Turing machines with bases in $\text{L}$ which are limited to a finite number of reversals (visits). For any full semiAFL $\text{L}$, FINITEREVERSAL ($\text{L}$) is the closure of $\text{L}$ under homomorphic replication or, equivalently, the closure of $\text{L}$ under iteration of controls on linear context-free grammars while FINITEVISIT ($\text{L}$) is the result of applying controls from $\text{L}$ to absolutely parallel grammars or, equivalently, the closure of $\text{L}$ under deterministic two-way finite state transductions. If $\text{L}$ is a full AFL with $\text{L}$ ≠ FINITEVISIT($\text{L}$), then FINITEREVERSAL($\text{L}$) ≠ FINITEVISIT($\text{L}$). In particular, for one-way checking automata, k + 1 reversals are more powerful than k reversals, k + 1 visits are more powerful than k visits, k visits and k + 1 reversals are incomparable and there are languages definable within 3 visits but no finite number of reversals. Finite visit one-way checking automaton languages can be accepted by nondeterministic multitape Turing machines in space log₂n. Results on finite visit checking automata provide another proof that not all context-free languages can be accepted by one-way nonerasing stack automata.     

Crosscorrelation between linearly and nonlinearly distorted versions of a given signal

A given deterministic signal x(.) is distorted by passing it through a linear time-invariant filter and also by subjecting it to the action of an instantaneous nonlinearity. The resulting time crosscorrelation of the two distorted versions of the original signal is expressed by the function

$\text{R}{}_2\text{(s)?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{g[x(t)]k(t?t′)x(t?s)dt dt′}$

, where x(.) is the given signal, k(.) is the nonnegative definite impulse response of the linear filter, and g(.) is the output-input characteristic of the zero-memory nonlinear device. The problem considered is that of determining conditions on the pair (x,g) such that R₂(s) ? R₂(0) for all s and any choice of nonnegative definite filter function k; the principal result is the formulation of a necessary and sufficient condition for R₂ to have a global maximum at the origin. In particular, the peak value occurs at the origin if and only if $\text{G}{}_{\mathrm{x}}{}^1\text{(ω)X(ω)}$ is real and nonnegative for all ω ? 0, where G_x(.) and X(.) are the Fourier transforms of g[x(.)] and x(.), respectively. An equivalent condition is that the correlation function

$\text{R}{}_2\text{(s)?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{g[x(t)]x(t?s)dt}$

, previously studied by Richardson, be nonnegative definite.Several examples are given, and it is shown that, unlike the case for R₁(.), monotonicity of g(.) is not a sufficient condition for R₂(.) to have a global maximum at s = 0 independently of the choice of filter characteristic k. Certain extensions of these results are given for the case when x(.) is a Gaussian random input.     

Qualitative relativizations of complexity classes

The principal result of this paper is a “positive relativization” of the open question “P = ?$\text{NP ? co-NP}$.” That is, the nondeterministic polynomial time-bounded oracle Turing machine endowed with designated accepting states and with designated rejecting states is considered, and suitable restrictions R of this device are developed such that $\text{P = NP ? co-NP}$ if and only if for every oracle D, P(D) = NP_R(D), where NP_R(D) is the class of languages L?NP(D) that are accepted by oracle machines operating with restrictions R. Positive relativizations are obtained for the P = ? $\text{U}$ ? co - $\text{U}$ and $\text{U}$ = ? NP questions also, where $\text{U}$ is the class of languages L in NP accepted by nondeterministic machines that operate in polynomial time and that have for each input at most one accepting computation. The restrictions developed here are “qualitative” in the sense that they restrict the form and pattern of access to the oracle. In contrast, a previous paper [3] developed quantitative relativizations-the number of distinct queries to the oracle is restricted-but no quantitative positive relativization of $\text{P = ? NP ? co-NP}$ is known.     

Finite difference representations of vorticity transport

Explicit finite difference representations of the steady two-dimensional laminar vorticity transport equation of fluid dynamics are summarized and discussed. The approximations known as ‘upwind differencing’, ‘locally exact’ after Alien and Southwell [1], Briggs [4] or Dennis and Hudson [12] are all shown to be the central difference approximation with the addition of numerical diffusion of the order of the error term in cell Reynolds number, R_c, which makes the associated matrix diagonally dominant. The local truncation error of this type of approximation can be minimized thus: (i) for ¦$\text{R}{}_{\mathrm{c}}\text{¦? 2}$, the central difference approximation, (ii) for ¦$\text{R}{}_{\mathrm{c}}\text{¦ > 2}$, upwind differencing applied to the inviscid equations, and therefore can be considered as a boundary layer approximation. This is the scheme introduced by Spalding [35]; successfully tested by Runchal [33].The local truncation error of the boundary condition, after Woods [39] for the vorticity is minimized in such a way that the formula is third-order accurate in grid size, in rectangular Cartesian coordinates.     

Random functions with given time correlation

First, on any sequence of real numbers (x_λ), $\text{λ ? [? Λ}{}_1\text{+ Λ] ?}\text{Z}$, the pseudo probability Pr(x, x′) of the event x_λ?[x, x′[ is defined to be the limit when Λ → ∞ of the ratio of the number of x_λ?[x, x′[ to the total number of x_λ. The a.d.f. (asymptotic distribution function) of the sequence is then defined by F(x) = Pr(? ∞, x); it possesses the properties of a d.f. (distribution function). Consequently, what is said below applies equally to a sequence of r.v. (random variables) or to a sequence of p.r.v. (pseudorandom variables) consisting of a sequence (_nx_λ), $\text{n ? [? N, + N] ?}\text{Z}$ of sequences _nx_λ, $\text{λ ? [? Λ, + Λ] ?}\text{Z}$.A weyl's polynomial ?_n(λ) is a polynomial such that one of its coefficieints other than ?(0) is irrational. Then any sequence, the fractional part of ?_n(λ), $\text{λ ? [? Λ, + Λ] ?}\text{Z}$, is asymptotically equidistributed on [0, 1].A property is given which permits the construction of a sequence (_nx_λ), $\text{n ? [? N, + N] ?}\text{Z}$ of pseudostochastically independent sequences _nx_λ, $\text{λ ? [? Λ, + Λ] ?}\text{Z}$.It is known that setting Y_n = F^{(? 1)}(X_n), it is possible to transform any sequence of r.v. X_n     

View azimuth and zenith,and solar angle effects on wheat canopy reflectance

Since crop canopies are not lambertian reflectors, their reflectance varies with sun and view positions. It is not always possible or convenient to make reflectance measurements from the nadir position nor at the same time of day. Therefore, ways of estimating nadir reflectance from off-nadir views and for various solar zenith angles are needed. In this study, spectral measurements were made with a Mark II radiometer five times during the day on each of four dates from 15° interval zenith and 45° azimuth positions for wheat canopies during the development interval stem extension to watery ripeness of the grain. The ratio of off-nadir [R(Z_v,A_v)] to nadir [R(0)] radiance in NIR band (0.76–0.90 μm) was described by the regression equation: $\text{R(Z}{}_{\mathrm{v}}\text{,A}{}_{\mathrm{v}}\text{)}\text{R(0)}\text{= 1.0 + [β}{}_0\text{+ β}{}_1\text{sin}\text{(}\text{A}{}_{\mathrm{v}}\text{2}\text{) + β}{}_2\text{(1/}\text{cos}\text{Z}{}_{\mathrm{s}}\text{)]}\text{sin}\text{Z}{}_{\mathrm{v}}$ where A_v is view azimuth angle relative to the sum position, Z_s is solar zenith angle, and Z_v is view zenith angle. The coefficient of determination was 0.70 or higher. The equation describes the observations that 1) the ratio of off-nadir to nadir radiance increases or decreases as view zenith angle increases depending on view azimuth angle; backscattering is stronger than forwardscattering and the pattern is azimuthally symmetric about the principal plane of the sun; and 2) the rate of change in the radiance ratio increases with increasing solar zenith angle. The coefficients, β₀, β₁ and β₂, changed as the canopies grew. Although the equation needs to be more fully tested, it should help summarize and compare various angular observation data taken in crop fields.     

Coping with known patterns of lies in a search game

In this paper we study a two-person search game in which player A thinks of a real number z?[0, 1), and player B asks Q questions of the yes/no answer type to confine z to a subset R_Q of as small a size as possible. The responses of player A to the queries of B need not all be true, but the nature of lie's characterized by a set $\text{X}$ of binary strings of length Q. We show that the smallest possible worst-case size of R_Q is 2^-Q|$\text{X}$|, and there exist algorithms for player B to achieve this. We also carry out an average-case analysis of the problem.     

Curved finite element methods for the solution of singular integral equations on surfaces in R3

We have shown in [1]that the singular integral equation (1.2) on a closed surface Γ of R³ admits a unique solution q and is variational and coercive in the Hilbert space $\text{H}{}^{\mathrm{<mtext>?</mtext><mtext>1</mtext><mtext>2</mtext>}}$(Γ). In this paper, with the help of curved finite elements, we introduce an approximate surface Γ_h, and an approximate problem on Γ_h, whose solution is q_h. Then we study the error of approximation |q ? q_h| in some Hubert spaces and also the associated error |u ? u_h| of the potential.