Matrix equations over rings

The main purpose of this work is to establish necessary conditions and sufficient conditions for the existence of a solution of matrix equations whose coefficient matrices have elements belonging to the ring $\text{R=}\text{C}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}$ of polynomials in n variables with complex coefficients and the ring $\text{R=}\text{R}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}{}^{\mathrm{n}}$ of rational functions a(z₁,z₂,…z_n)b(z₁,z₂,…,z_n)^?1 with real coefficients and b(z₁,z₂,…,z_n)≠0 for all (z₁,z₂,…,z_n) in Rⁿ. Results obtained are useful in multidimensional systems theory and elsewhere.     

On the prediction of band-limited signals from past samples

A new method is used to construct coefficients a_kn such that any band-limited signal function with highest frequency ΠW can be reconstituted from its samples from the past via

$\text{?(t)=}\text{lim}\text{n→∞}\text{σ}\text{k=1}\text{n}\text{a}{}_{\mathrm{kn}}\text{?}\text{t?}\text{kT}\text{W}$

Although the existence of such predictor coefficients can be proved for each positive T < 1, so far they have been exhibited only for $\text{T ? (0,}\text{built1}\text{2}\text{)}$ by J. L. Brown, Jr. [1]. Using the mathematical tool of power series expansions in the complex domain, T can be extended to at least $\text{T <}\text{1}\text{2}$, that is, the sampling rate has to exceed three-halves the Nyquist rate. Again the predictor coefficients a_kn do not depend on the structure of ? or on the bandwidth parameter W.     

The time-precision tradeoff problem on on-line probabilistic Turing machines

A probabilistic Turing machine (PTM) is a Turing machine that flips an unbiased coin to decide its next movement and solves a problem with some error probability. It is expected that PTMs need more time if a smaller error probability is required. This is a sort of time-precision tradeoff and is shown to occur actually on on-line probabilistic Turing machine acceptors (ONPTMs). That is, we show the existence of a set such that it is recognized by an ONPTM with $\text{1}\text{2}\text{-(}\text{log}\text{n)/}\text{8}\text{n}$ bounded error probability in O(n) time but for every $\text{ε, 0<ε<}\text{1}\text{2}$, it requires more than O((n/log n)²) time to recognize this set with bounded error probability by ONPTMs. Moreover our result is also shown to be an example of difference between nondeterministic computations and probabilistic ones.     

Truncations of infinite matrices and algebraic series associated with some of grammars

We consider an algebraic system over $\text{R}$[x] of the form X = a₀(x)X^k+ a_k1(x)X+a_k(x), where a₀(x) and a_k(x) are in x$\text{R}$[x] and a_k?1(x) is in x$\text{R}$. Let A be the infinite incidence matrix associated with the algebraic system. Then we prove that the eigenvalues of northwest corner truncations of A are dense in some algebraic curves.Using this we get a result on positive algebraic series. We consider the case that the coefficients of a₁(x)(i = 0,…,k?1, k) are positive. The algebraic series generated by the algebraic system may be viewed as a function in the complex variable x. Then by the above fact we prove that the radius of convergence of the function equals the least positive zero of the modified discriminant of the system.As an application to context free languages we show a procedure for calculating the entropy of some one counter languages. Other applications to Dyck languages and the Lukasiewicz language are also described.     

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     

Maximum principle and uniform convergence for the finite element method

The solution of the Dirichlet boundary value problem over a polyhedral domain Ω ? Rⁿ, n ≥ 2, associated with a second-order elliptic operator, is approximated by the simplest finite element method, where the trial functions are piecewise linear. When the discrete problem satisfies a maximum principle, it is shown that the approximate solution u_h converges uniformly to the exact solution u if u ? W_1,p (Ω), with p > n, and that $\text{∥u?u}{}_{\mathrm{h}}\text{∥}{}_{\mathrm{L}}\text{∞(Ω) = O(h)}$ if u ? W²,p(Ω), with 2p > n. In the case of the model problem ?Δu+au = f in Ω, u = u_o on δΩ, with a ? 0, a simple geometrical condition is given which insures the validity of the maximum principle for the discrete problem.     

Approximate storage utilisation of B-trees: A simple derivation and generalisations

A new, intuitive derivation of the approximate average storage utilisation of B-trees is presented, which is generalised to the analysis of B¹-trees whose average storage utilisation is found to be $\text{≈ 2 l}\text{n}\text{(}\text{3}\text{2}\text{)}$ or 81%. The approximate average storage utilisation of trees with arbitrary minimum fullness factor f(0 <f<1) is also obtained and found to be $\text{f11}\text{n}\text{(}\text{1}\text{f}\text{)}\text{(1?f)}$.     

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.     

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.     

A probabilistic algorithm for vertex connectivity of graphs

A probabilistic algorithm is presented which computes the vertex connectivity of an undirected graph G = (V,E) in expected time $\text{O((-log ε|V|}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{|E|)}$ with error probability at most e provided that |E|<frcase|1/2d|V|² for some universal constant d<1.     

Evaluation and comparison of two efficient probabilistic primality testing algorithms

We analyse two recent probabilistic primality testing algorithms; the first one is derived from Miller [6] in a formulation given by Rabin [7], and the second one is from Solovay and Strassen [9]. Both decide whether or not an odd number n is prime in time O(m, lognM(n)) with an error probability less than α^m, for some $\text{0≤a<}\text{1}\text{2}$. Our comparison shows that the first algorithm is always more efficient than the second, both in probabilistic and algorithmic terms.     

Entropy and set covering

If the set covering constraints are Ax ? 1 and x_j ∈ {0,1}, the prior probability that the jth subset participates in an optimal covering (independently of subset costs) is shown to be given by the principal row eigenvector of A¹A, where $\text{a}{}_{\mathrm{ji}}{}^1\text{= 1 ? a}{}_{\mathrm{ij}}$. These probabilities lead to new and interesting objective functions, which are shown to be equivalent to cross entropy or weighted cross-entropy. The probabilities can also be used to obtain better bounds for heuristic solutions to optimal covering and set representation problems.     

On the stability of convolution feedback systems with dynamical feedback

This paper considers distributed n-inputn-output convolution feedback systems characterized by $\text{y = G}{}_1\text{1e}$, $\text{z = G}{}_2\text{1y}$ and e = u ? z, where the forward path transfer function $\text{G}\text{?}{}_1$ and the feedback path transfer function $\text{G}\text{?}{}_2$ both contain a real single unstable pole at different locations. Theorem 1 gives necessary and sufficient conditions for both input-error and input-output stability. In addition to usual conditions that guarantee input-error stability a new condition is found which results in the fact that input-error stability will guarantee input-output stability. These conditions require to investigate only the open-loop characteristics. A basic device is the consideration of the residues of different transfer functions at the open-loop unstable poles. An example is given.     

Multiplicity of positive solutions of a class of nonlinear fractional differential equations

This paper is concerned with the nonlinear fractional differential equation L(D)u=f(x,u), u(0)=0, 0<x<1,where L(D) = Dsn − an−1Dsn−1 − … − a1Ds11 < s2 < … < sn < 1, and aj > 0, j = 1,2,…, n − 1. Some results are obtained for the existence, nonexistence, and multiplicity of positive solutions of the above equation by using Krasnoselskii's fixed-point theorem in a cone. In particular, it is proved that the above equation has N positive solutions under suitable conditions, where N is an arbitrary positive integer.     

Asymptotic behavior of nonoscillatory solutions of neutral difference equations

The authors consider the m^th-order neutral difference equation D_m(y(n) + p(n)y(n − k) + q(n)f(y(σ(n))) = e(n), where m ≥ 1, {p(n)}, {q(n)}, {e(n)}, and {a₁(n)}, {a₂(n)}, …, {a_m−1(n)} are real sequences, a_i(n) > 0 for i = 1,2,…, m−1, a_m(n) ≡ 1, D₀z(n) = y(n)+p(n)y(n − k), D_iz(n) = a_i(n)ΔD_i−1z(n) for i = 1,2, …, m, k is a positive integer, {σ(n)} → ∞ is a sequence of positive integers, and R → R is continuous with u f(u) > 0 for u ≠ 0. In the case where {q(n)} is allowed to oscillate, they obtain sufficient conditions for all bounded nonoscillatory solutions to converge to zero, and if {q(n)} is a nonnegative sequence, they establish sufficient conditions for all nonoscillatory solutions to converge to zero. Examples illustrating the results are included throughout the paper.