Properties of structure generating functions of automata and their applications for linear systems

We show a relation between the structure generating functions of $\text{R}$-x-automata and solutions of linear equations. When we take the function as the set of the paths of the automaton, we can use the paths as a useful tool for analyzing linear systems. As an application of this theory, we get Mason's formula on a signal flow graph. Next we consider an $\text{R}$-x-automaton with infinite states and extend Mason's formula to an infinite matrix. Besides for any infinite matrix A, we define det(E ? xA) in two different ways, and show that the two definitions coincide in some cases.     

Kleene chain completeness and fixedpoint properties

Let L denote the nonscalar complexity in k(x₁,…, x_n). We prove $\text{L(?,??/?x}{}_1\text{,…,??/?x}{}_{\mathrm{n}}\text{)?3L(?)}$. Using this we determine the complexity of single power sums, single elementary symmetric functions, the resultant and the discriminant as root functions, up to order of magnitude. Also we linearly reduce matrix inversion to computing the determinant.     

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     

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.     

Information storage and retrieval — mathematical foundations II (combinatorial problems)

The following combinatorial problem is fundamental for the design of file organizations minimizing simultaneously the storage space and the access time: For a given family $\text{M}$ of subsets of a finite set X, find a partial function S:X→X (if there is one), such that every M?$\text{M}$ can be written as M=lcubx,S(x),?,S^|M|-1 (x)rcub for a suitable x?X. We study the class of families admitting such a function S, as well as some of its subclasses defined by imposing certain restrictions on S (these restrictions reflect the structure of the storage medium to be used for storing a file).     

Torsion problem for elastic cylinder with inserts and holes

An integral equation method to solve the classical torsion problem for an elastic cylinder with inserts and holes is treated. The bounded region outside the inserts and the holes will be termed a matrix. As is well-known the solution depends on finding plane harmonic functions in the matrix and inserts such that (a) on the outer boundary of the matrix and the boundaries of the holes the harmonic function in the matrix takes the values $\text{1}\text{2}\text{(x}{}^2\text{+y}{}^2\text{)+c}{}_{\mathrm{j}}$, and (b) on the interfaces of the matrix and the inserts relations exist between the harmonic functions and between their normal derivatives. Here (x, y) are the coordinates of the point on the boundary and c_j, are unknown constants. The usual methods are cumbersome and lengthy. In this paper a straightforward method is presented which is easily programmable. The numerical solution is obtained by evaluating a few integrals either analytically or numerically and solving a system of linear simultaneous equations. An example of a cylinder with an eccentric insert is given which substantiates the theory developed in this paper and is found to agree with known results. However, the method is general and may be applied to a variety of problems.     

An algorithm for inverse square-roots

An algorithm is presented for finding $\text{x}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}$, given x. The algorithm is designed to be particularly suited for parallel computation, in which floating-point multiplication, floating-point addition and fixed-point arithmetic can be performed simultaneously.     

An upper bound on the mean-square error in the sampling expansion for non-band-limited processes

An upper bound is obtained on the mean-square error involved when a real-valued non-band-limited nonstationary random process x(t) is approximated by the sampling expansion

$\text{∑}\text{n=?∞}\text{∞}\text{x(nT)}\text{sin}\text{π(t?nT)/T}\text{π(t?nT)/T}$

for some T > 0. When the process x(t) is band-limited over [$\text{?}\text{1}\text{2T}\text{,}\text{1}\text{2T}$], this error bound reduces to zero.     

Curve generation of implicit functions by incremental computers

The conventional numerical solution of an implicit function f(x, y) = 0 is substantially complicated for calculating by any computer. We propose a new method representing the argument of the implicit function as a unary function of a parameter, t, if the continuous and unique solution of f(x, y) = 0 exists. The total differential $\text{d}\text{f}\text{d}\text{t}$ constitutes simultaneous differential equations of which the solution about x and y is unique. The Newton-Raphson method must be used to calculate the values near singular points of an implicit function and then the sign of dt has to be decided according to four special cases. Incremental computers are suitable for curve generation of implicit functions by the new method, because the incremental computer can perform more complex algorithms than the analog computer and can calculate faster than the digital computer. This method is easily applicable to curve generation in three-dimensional space.     

A recursive and a grammatical characterization of the exponential-time languages

We characterize the class of all languages which are acceptable in exponential time by means of recursive and grammatical methods. (i) The class of all languages which are acceptable in exponential time is uniquely characterized by the class of all (0-1)-functions which can be generated, starting with the initial functions of the Grzegorczyk-class $\text{E}$², by means of subtitution and limited recursion of the form f(x, y + 1) = h(x, y), f(x, y), f(x, l(x, y))), l(x, y) ? y. (ii) The class of all languages which are acceptable in exponential time is equal to the class of all languages generated by context-sensitive grammars with context-free control sets.     

An algorithm for the computation of the transfer function matrix for singular systems

For singular systems, i.e. for systems of the form $\text{E}\text{x}\text{?}\text{= Ax + Bu}$, with E singular, the problem of computing the transfer function matrix has been solved. An algorithm is developed which uses the Souriau-Frame-Faddeev algorithm for regular systems. The final expression is suitable for computer use.     

Solution errors in finite element analysis

The development of the finite element method so far indicates that it is a discretization technique especially suited for positive definite, self-adjoint, elliptic systems, or systems with such components. The application of the method leads to the discretized equations in the form of $\text{u}\text{?}\text{=}\text{f(u)}$, where u lists the response of the discretized system at n preselected points called nodes. Instead of explicit expressions, vector function f and its Jacobian f,_u are available only numerically for a numerically given u. The solution of $\text{u}\text{?}\text{=}\text{f(u)}$ is usually a digital computer. Due to finiteness of the computer wordlength, the numerical solution $\text{u}{}_{\mathrm{c}}$ is in general different from u. Let $\text{u}\text{(}\text{x}\text{, t)}$ denote the actual response of the system in continuum at points corresponding to those of u. In the literature. $\text{u}\text{(}\text{x}\text{, t)-}\text{u}$ is called the discretization errors, $\text{u}\text{-}\text{u}{}_{\mathrm{c}}$ the round-off errors, and the s is. $\text{u}\text{(}\text{x}\text{, t)-}\text{u}{}_{\mathrm{c}}$ is called the solution errors. In this paper, a state-of-the-art survey is given on the identification, growth, relative magnitudes, estimation, and control of the components of the solution errors.     

On the complexity of simple arithmetic expressions

Let $\text{E}$ be the set of all simple arithmetic expressions of the form E(x) = xT_l…T_k where x is a nonnegative integer variable and each T_i is a multiplication or integer division by a positive integer constant. We investigate the complexity of the inequivalence and the bounded inequivalence problems for expressions in $\text{E}$. (The bounded inequivalence problem is the problem of deciding for arbitrary expressions E₁(x) and E₂(x) and a positive integer l whether or not E₁(x) ≠ E₂(x) for some nonnegative integer x<l. If l = ∞, i.e., there is no upper bound on x, the problem becomes the inequivalence problem.) We show that the inequivalence problem (or equivalently, the equivalence problem) for a large subclass of $\text{E}$ is decidable in polynomial time. Whether or not the problem is decidable in polynomial time for the full class $\text{E}$ remains open. We also show that the bounded inequivalence problem is NP-complete even if the divisors are restricted to be equal to 2. This last result can be used to sharpen some known NP-completeness results in the literature. Note that if division is rational division, all problems are trivially decidable in polynomial time.     

On the time-space tradeoff for sorting with linear queries

Extending a result of Borodin et al. [1], we show that any branching program using linear queries “∑_iλ_ix_i:c” to sort n numbers x₁, x₂,…,x_n must satisfy the time-space tradeoff relation $\text{TS = Ω(n}{}^2\text{)}$. The same relation is also shown to be true for branching programs that uses queries “min R = ?” where R is any subset of {x₁, x₂,…,x_n}.     

PRP: a FORTRAN IV interactive plotting program

A computer program, PRP, has been designed to plot any arithmetic combination selected from a set of major and trace element data on a y-x graph. y and x are defined and entered as a program string (y, x) which is interpreted sequentially. Operators ($\text{+, -, 1, /, (}\text{unary}\text{)}$, square root, log₁₀, In_c, antilog₁₀, exponential, integer, absolute value, (,),,) and integer or real numbers may be included. Axis lengths and scales are determined by the user. Five different plotting symbols are available.     

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.