Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

Shallow circuits and concise formulae for multiple addition and multiplication

A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several different representation standards.The construction of some new carry-save adders is described. Using these carry-save adders optimally, as prescribed by the above theory, we get {, , }-circuits of depth 3.48 log₂ n and {, , }-circuits of depth 4.95 log₂ n for the carry-save addition ofn numbers of arbitrary length. As a consequence we get multiplication circuits of the same depth. These circuits put out two numbers whose sum is the result of the multiplication. If a single output number is required then the depth of the multiplication circuits increases respectively to 4.48 log₂ n and 5.95 log₂ n.We also get {, , }-formulae of sizeO (n ^3.13) and {, }-formulae of sizeO (n ^4.57) for all the output bits of a carry-save addition ofn numbers. As a consequence we get formulae of the same size for the majority function and many other symmetric Boolean functions.     

The dynamic clusters method in nonhierarchical clustering

Given a finite setE R ⁿ, the problem is to find clusters (or subsets of similar points inE) and at the same time to find the most typical elements of this set. An original mathematical formulation is given to the problem. The proposed algorithm operates on groups of points, called samplings (samplings may be called multiple centers or cores); these samplings adapt and evolve into interesting clusters. Compared with other clustering algorithms, this algorithm requires less machine time and storage. We provide some propositions about nonprobabilistic convergence and a sufficient condition which ensures the decrease of the criterion. Some computational experiments are presented.     

Choosing reference classes and building provisional models

A well-known problem in default logic is the ability of naive reasoners to explain bothg and ¬g from a set of observations. This problem is treated in at least two different ways within that camp.One approach is examination of the various explanations and choosing among them on the basis of various explanation comparators. A typical comparator is choosing the explanation that depends on the most specific observation, similar to the notion of narrowest reference class.Others examine default extensions of the observations and choose whatever is true in any extension, or what is true in all extensions or what is true in preferred extensions. Default extensions are sometimes thought of as acceptable models of the world that are discarded as more knowledge becomes available.We argue that the notions of specificity and extension lack clear semantics. Furthermore, we show that the problems these ideas were supposed to solve can be handled easily within a probabilistic framework.     

Modelling default and likelihood reasoning as probabilistic reasoning

This paper presents a probabilistic analysis of plausible reasoning about defaults and about likelihood. Likely and by default are in fact treated as duals in the same sense as possibility and necessity. To model these four forms probabilistically, a logicQDP and its quantitative counterpartDP are derived that allow qualitative and corresponding quantitative reasoning. Consistency and consequence results for subsets of the logics are given that require at most a quadratic number of satisfiability tests in the underlying prepositional logic. The quantitative logic shows how to track the propagation error inherent in these reasoning forms. The methodology and sound framework of the system highlights their approximate nature, the dualities, and the need for complementary reasoning about relevance.Much of this research was done while at the University of Technology, Sydney, Broadway, NSW, Australia, and some at the Turing Institute, 36 Nth. Hanover Str., Glasgow, Scotland.     

Hierarchy theorems for two-way finite state transducers

Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL⁰()= and for n0, CAL ⁿ⁺¹()=CAL ⁿ (CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL ⁿ () forms a proper hierarchy and for every n0, FINITE · VISIT(CALⁿ()) CAL ⁿ⁺¹() FINITE · VISIT(CAL ⁿ⁺¹()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and ₁ is a full semiAFL, then is contained in CAL^m(₁) if and only if it is contained in ₁. Among the applications of these results are the following. For the following families , CAL ⁿ () forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL ^m (NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL ^m (STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725     

Context-free text grammars

A text is a triple=(, ₁, ₂) such that is a labeling function, and ₁ and ₂ are linear orders on the domain of ; hence may be seen as a word (, ₁) together with an additional linear order ₂ on the domain of . The order ₂ is used to give to the word (, ₁) itsindividual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introducecontext-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of ashapely context-free text grammar also investigated in this paper.     

Deterministic sequential functions

The simple rational partial functions accepted by generalized sequential machines are shown to coincide with the compositions _P ^–1 , where _P consists of the prefix codings. The rational functions accepted by generalized sequential machines are proved to coincide with the compositions _P ^–1 , where is the family of endmarkers and is the family of removals of endmarkers. (The compositions are read from left to right). We also show that _P ^–1 is the family of the subsequential functions.This work was partially supported by the Esprit Basic Research Action Working Group No. 3166 ASMICS, the CNRS and the Academy of Finland     

Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a circle at infinity given by a planeP and a range of angles {(t)¦t[01]} [02]. At timet, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angle(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.The second author was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

The mixing properties of certain processes related to Markov chains

Summary Let {Y _n ,– < n < } be either a function of a stationary Markov chain with countable state space, or a finitary process in the sense of Heller [3]. The purpose of this note is to prove that if {Y _n ,– < n < } is mixing, then it is aK-shift. (Definitions will be given below.)IfT is a measure-preserving transformation on a probability space, then the following implications relevant to the present paper are known: (1)T is aK-shift T is (r + 1)-mixing T isr-mixing T is totally ergodic T is ergodic, and (2)T is ergodic T is totally ergodic T isr-mixing T is aK-shift.It is not known if the classes ofr-mixing and (r + 1)-mixing transformations are distinct. (1-mixing is also called mixing.) The results of this note then imply that for the classes of transformation that we are consideringr-mixing and (r + 1)-mixing are equivalent.This research was partially supported by NSF Grant GP-19660.     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

An extension of the theory of learning systems

Summary The author's inquiry [1] on learning systems is generalized in the following respects: The process of learning, instead of coming to an end when the learning goal has been reached, is supposed to last for ever, so that the above definitive learning as well as phenomena such as forgetting, re-learning, changing the goal etc. become describable.We take over the notion of semi-uniform solvability of a set of learning problems (2.2), but now (trivial cases excluded) the whole capacity of a learning system is never s. u. solvable. Finite such sets are. The notion of a solving-basis of some is introduced and we can state necessary conditions that possess such a basis (2.14), so that examples of sets without a basis can be provided. On the other hand, any s. u. solvable has as basis. The notion of uniform solvability (3.1) reinforces that of s. u. solvability, and there are given sufficient conditions for to be uniformly solvable (3.6). In some finite cases, s. u. solvability, existence of a basis and uniform solvability coincide (3.7–3.9). At last we give the construction for the weakest learning system solving a uniformly solvable problem set (3.12–3.19).Eine deutsche Fassung wurde am 30. Mai 1972 eingereicht.     

A note on dimensions and factors

In this short note, we discuss several aspectsof dimensions and the related constructof factors. We concentrate on those aspectsthat are relevant to articles in this specialissue, especially those dealing with the analysisof the wild animal cases discussed inBerman and Hafner's 1993 ICAIL article. We reviewthe basic ideas about dimensions,as used in HYPO, and point out differences withfactors, as used in subsequent systemslike CATO. Our goal is to correct certainmisconceptions that have arisen over the years.     

Determining literariness in interactive fiction

The authors of interactive fiction are beginning to demonstrate a concern for the literariness of their product. Literariness, as defined by Shklovskij and the Russian Formalists, is the quality of making strange that which is linguistically familiar, a quality Shklovskij termed ostranenie. By applying the principle of ostranenie, as well as other well-known literary principles, to the most serious interactive fictions, we can determine if this new genre exhibits the features of literariness. A study of Mindwheel, Brimstone, Breakers, A Mind Forever Voyaging, Portal, and Trinity suggest that the literariness of interactive fiction comes out of its concern both for making strange what is familiar and for making familiar what is strange.Neil Randall has published several role-playing games, and is working on a full-length critical study of interactive fiction. He is currently assistant professor of English.     

Linear Interval Tolerance Problem and Linear Programming Techniques

In this paper, we consider the linear interval tolerance problem, which consists of finding the largest interval vector included in ([A], [b]) = {x R ⁿ | A [A], b [b], Ax = b}. We describe two different polyhedrons that represent subsets of all possible interval vectors in ([A], [b]), and we provide a new definition of the optimality of an interval vector included in ([A], [b]). Finally, we show how the Simplex algorithm can be applied to find an optimal interval vector in ([A], [b]).     

Sufficiency conditions for existence of an optimal feedback control in stochastic mechanics

In the framework of stochastic mechanics, the following problem is considered: in a set of admissible feedback controls v, with range inE ⁿ , find one minimizing the expectationE _sx { _s ^T L(t, (t), (t, (t)))dt + W _T ((T))} for all (s, x) [0,T) E ⁿ , whereL(t, x, ) = (/12)m ² – U(t, x) is the classical action integrand and is an-dimensional diffusion process in the weak sense, (see Bensoussan, 1982) with drift and diffusion coefficientD constant > 0.W _T andU are given real functions. Sufficiency conditions for the existence of such an optimal feedback control are given. Dedicated to George Leitmann Recommended by G.J. Olsder Presented at the Third Workshop on Control Mechanics in honor of George Leitmann, January 22–24, 1990, University of Southern California, Los Angeles, California (USA).     

Maintaining Longest Paths Incrementally

Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. This paper considers invariants for longest paths in directed acyclic graphs, a fundamental abstraction for many applications. It presents bounded incremental algorithms for arc insertion and deletion which run in O( + || log||) time and O() time respectively, where || and are measures of the change in the input and output. The paper also shows how to generalize the algorithm to various classes of multiple insertions/deletions encountered in scheduling applications. Preliminary experimental results show that the algorithms behave well in practice.     

Symbolic computation of robot models for geometric parameters identification with singularity analysis

The computation of the geometrical parameters identification model of a robot arm leads to an intrinsic extended Jacobian matrix. This matrix is often singular and its manual computation is tedious and may lead to error. A computer assisted procedure is developed to compute this matrix symbolically and to check its singularity. The program GPIM is developed in Pascal and works on PC's for this purpose. Jacobian singularity is checked using its symbolic expressions with the aid of a proposed table for robot arm parameters to obtain a minimum set of identified parameters. This program can be used for simple chain robot arms having revolute (R) and/or prismatic (P) joints including the case of consecutive near parallel axes. TH8 robot arm of type RPPRRR having two pairs of consecutive near parallel axes is studied to show the program efficiency and how singularity is eliminated.Nomenclature a _i Denavit-Hartenberg parameter. - C _i ,C _i andC ₁₂ cos _i , cos _i and cos ( ₁ + ₂). - J ₀, J Basic Jacobian and Jacobian matrices. - J _a , J _r , J , J and J Sub-Jacobian matrices. - J _0a , J _0r , J ₀, J ₀ and J ₀ Intrinsic sub-Jacobian matrices. - m Work space dimensions. - n Number of moving links of the robot arm. - p Number of pairs of consecutive near parallel axes. - P _i,i+1 and P _li [3×1] position vectors. - Q _pi , Q _ai , Q _ri , Q _i , Q _i and Q _i [4×4] differential operator matrices. - r _i Denavit-Hartenberg parameter. - R _l , R _i , R _i+1 and R _n+1 Base, links i–1, i and n coordinate frames. - R _i,i+1 and R _1i [3×3] orientation matrices. - S _i , S _i and S ₁₂ sin _i , sin _i and sin ₁ + ₂. - T _i,i+1 and T _1i [4×4] homogeneous transformation matrices. - X [m×1] robot arm operational coordinates. - 1st columns of the orientation matrices, and associated tensors. - 2nd columns of the orientation matrices, and associated tensors. - 3rd columns of the orientation matrices, and associated tensors. - _i Denavit-Hartenberg parameter. - _i Twist angle parameter. - X Changes in robot arm operational coordinates. - , ls and rr Changes in robot arm geometrical parameters, and their least square and ridge regression estimated changes. - _i Denavit-Hartenberg parameter. - , ^c and ⁿ Robot geometrical parameters and their correct and nominal values. - pi, ai, ri, i, i and i [4×4] differential operator matrices. - and ^–1 [3×3] conversion matrix and its inverse.     

Almost surely continuous solutions of a nonlinear stochastic integral equation

A nonlinear stochastic integral equation of the Hammerstein type in the formx(t; ) = h(t, x(t; )) + _s k(t, s; )f(s, x(s; ); )d(s) is studied wheret S, a measure space with certain properties, , the supporting set of a probability measure space (,A, P), and the integral is a Bochner integral. A random solution of the equation is defined to be an almost surely continuousm-dimensional vector-valued stochastic process onS which is bounded with probability one for eacht S and which satisfies the equation almost surely. Several theorems are proved which give conditions such that a unique random solution exists. AMS (MOS) subject classifications (1970): Primary; 60H20, 45G99. Secondary: 60G99.