A method for the calculation of eigenfunction expansions

In this paper, a method is presented for the calculation of the coefficients of the series expansion of a function f(t), in the base orthonormal set made up by the eigenfunctions of the self-adjoint operator $\text{L: L(x(t)) = (}\text{d}\text{dt}\text{)( p(t)(}\text{dx(t)}\text{dt}\text{))?q(t)x(t)}$. We show that the values of the numbers $\text{t}\text{}$x_k> can be obtained by solving the differential equation L + λ) y(t) = Kf(t), in the interval of definition, for each of the eigenvalues λ of L and by using as initial conditions those which determine one of its associated orthonormal functions. This makes the method specially interesting for its implementation on a hybrid computer: One advantage of the proposed method is that the analysis of f(t) does not require the simultaneous presence of the functions of the base set and the problem signal, thus eliminating both the problems of the synchronized generation of signals and the need for storing it in memory.     

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.     

Truncation error for band-limited nonstationary processes

Let x(t) be a real-valued random process band-limited to the interval [$\text{?1}\text{2T}\text{,}\text{1}\text{2T}$] for some T > 0. In this note we find an upper bound on the mean square of the truncation error involved when x(t) is approximated in the interval $\text{|t| ?}\text{T}\text{2}$ by the finite selection

$\text{∑}\text{n=?N}{}_1\text{N}{}_2\text{x(nt)}\text{sin}\text{π(t?nT)}\text{T}\text{π(t?nT)}\text{T}$

of terms from its sampling expansion representation.     

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.     

Knowledge versus search: A quantitative analysis using A1

This paper analyzes the average number of nodes expanded by $\text{A1}$ as a function of the accuracy of its heuristic estimates, by treating the errors h1 - h as random variables whose distribution may vary over the nodes in the graph. The search model consists of an m-ary tree with unit branch costs and a unique goal state situated at a distance N from the root.The main result states that if the typical error grows like φ(h1) then the mean complexity of $\text{A1}$ grows approximately like G(N)exp[cφ(N)], where c is a positive constant and G(N) is O(N²). Thus, a necessary and sufficient condition for maintaining polynomial search complexity is that $\text{A1}$ be guided by heuristics with logarithmic precision, e.g. φ(N) = (log N)^k. $\text{A1}$ is shown to make much greater use of its heuristic knowledge than a backtracking procedure would under similar conditions.     

Improving loops and vanishing variables in long transportation problems

In this paper the following two results are presented: (1)A method which determines the optimal values of certain variables during the iterative solution process. The closer the current primal feasible solution is to the optimal solution, the greater the number of variables which may be determined. (2) For each current feasible solution (X_ij) of the given m × n transportation problem A, a feasible solution ($\text{X}\text{?}{}_{\mathrm{ij}}$) of an auxiliary m × m(m ?1) transportation problem $\text{A}\text{?}$ is constructed. Problem $\text{A}\text{?}$ is shown to be equivalent to an m(m ? 1) × m(m ? 1) assignment problem with two admissible cells per column. The optimally of (X_ij) is shown to imply the optimality of ($\text{X}\text{?}{}_{\mathrm{ij}}$) and conversely. The best “improving loops” (including the improving loops used in MODI) of $\text{A}\text{?}$ are shown to be the best “improving loops” of A as well.     

Decidable sentences of Church-Rosser congruences

A decision procedure for a class of true sentences of congruences generated by finite monadic Church-Rosser systems is developed. Using this decision procedure it is shown that if $\text{M}$_T is the monoid presented by such a system T, then (i) it is decidable given T whether $\text{M}$_T is a group, (ii) it is decidable given T and a finite set A whether the submonoid generated by A is a group or a left (right, two-sided) ideal, and (iii) Green's relations for $\text{M}$_T are decidable.     

Closure systems and L-subalgebras

Let X be a set and ? a class of L-subsets of X. ? is a “closure system” if it is closed with respect to greatest lower bounds. If $\text{?}$ is an L-subset, then the g.l.b. $\text{}\text{?}$tf of {$\text{g ? ?|g??}$} is said to be generated by $\text{?}$. We examine closure systems of L-subalgebras and propose formulas for the L-subalgebra of a required type generated by a given L-subset.     

A note on ‘geometric transforms’ of digital sets

We define a ‘geometric transform’ on the digital plane as a function ? that takes pairs (P, S), where S is a set and P a point of S, into nonnegative integers, and where $\text{?(S, P)}$ depends only on the positions of the points of S relative to P. Transforms of this type are useful for segmenting and describing S. Two examples are ‘distance transforms’, for which $\text{?(S, P)}$ is the distance from P to S, and ‘isovist transforms’, where $\text{?(S, P)}$, is the area of the part S visible from P. This note characterizes geometric transforms that have certain simple set-theoretic properties, e.g., such that $\text{?(S?T,P) = ?(S,P)∧?(T,P)}$ for all S, T, P. It is shown that a geometric transform has this intersection property if and only if it is defined in a special way in terms of a ‘neighborhood base’; the class of such ‘neighborhood transforms’ is a generalization of the class of distance transforms.     

Point pattern matching by relaxation

Let $\text{P}\text{= P}{}_1\text{, …, P}{}_{\mathrm{m}}$ and $\text{Q}\text{= Q}{}_1\text{, …, Q}{}_{\mathrm{n}}$ be two patterns of points. Each pairing (P_i, Q_j) of a point of $\text{P}$ with a point of $\text{Q}$ defines a relative displacement δ_ij of the two patterns. We can define a figure of merit for δ_ij according to how closely other point pairs coincide under δ_ij. If there exists a displacement δ₀ for which $\text{P}$ and $\text{Q}$ match reasonably well, the pairings for which δ_ij ? δ₀ will have high merit scores, while other pairings will not. The scores can then be recomputed, giving weights to the other point pairs based on their own scores; and this process can be iterated. When this is done, the scores of pairs that correspond under δ₀ remain relatively high, while those of other pairs become low. Examples of this method of point pattern matching are given, and its possible advantages relative to other methods are discussed.     

Circuit size is nonlinear in depth

Two fundamental complexity measures for a Boolean function f are its circuit depth d(f) and its circuit size c(f). It is shown that $\text{c?}\text{1}\text{4}\text{d·}\text{log}{}_2\text{d}$ for all f.     

2DST mappings on languages and related problems

Let $\text{l}$ be a family of languages effectively closed under inverse homomorphism and intersection with regular sets and such that the languages have effectively constructible semilinear Parikh maps. We show that there is an algorithm to decide given a language L in $\text{L}$ and a language R accepted by a one-way nondeterministic multicounter machine, where each counter makes exactly one reversal, whether L∩R is empty. This result has many applications. In particular, it can be used to show that there is an algorithm to decide given a language L in $\text{L}$ and two-way deterministic sequential transducers (2DST's) S₁ and S₂ whether S₁ and S₂ are equivalent on L.     

A heuristic search algorithm with modifiable estimate

This paper describes an improved version of two previously published algorithms in the area: $\text{A1}$ and B. The new approach is based on considering the estimate ?(n) on node n as a variable rather than as a constant. The new algorithm thus improves the estimate as it goes on, avoiding some useless node expansions. It is proved to never expand more nodes than B or $\text{A1}$ and to expand a much smaller number of them in some cases.Another result of the paper is a proof that no overall optimal algorithm exists if the cost of an algorithm is measured by the total number of node expansions.     

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.     

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)}$.     

Pattern recognition: The categorical setting

We present in this paper the categorical setting for patterns and pattern recognition, bringing together several of our previous results and unifying the algebraic syntactic-oriented, automata-theoretical, and topological formalisms. After briefly recalling these formalisms and terminology, we first show under which conditions images $\text{I}{}_{\mathrm{\mu }}\text{?}\text{I}$ and deformations δ?Δ can be organized in a category $\text{(}\text{I}\text{,Δ) =}\text{I}{}^{\mathrm{\Delta }}$, and how one can associate with it a recognition category $\text{(}\text{I}\text{,Γ) =}\text{I}$, where Γ is a group of similarities γ?Γ included in Δ. Probes and recognition functions are characterized as being invariant functors of categories, and a particular class of probes—projections—is studied using the notion of retract of a category; this notion is then used to characterize the family ? of patterns. The relationship between $\text{I}$, $\text{I}$^Δ, and ? is described. Further investigation of recognition in $\text{I}$ is performed by exhibiting the practical meaning of retracts along with their lifting properties. Furthermore, the recognition problem associated with the initial deformed image category $\text{I}$^Δ is studied, introducing the skeleton Σ of $\text{I}$^Δ; the role played by retracts is again emphasized. Finally we present the connection between patterns, projections and, skeletons; the link existing between the present formalism and current application; and the topological explanation of the “useful” properties of projections and skeletons. The paper ends by listing some open research problems.