Unifications,deunifications, and their complexity

The execution of a Prolog program can be viewed as a sequence of unifications and backtracks over unifications. We study the time requirement of executing a sequence of such operations (the unify-deunify problem). It is shown that the well-known set union problem is reducible to this problem, even in the case when no function symbols are allowed (the Datalog unify-deunify problem). As the set union problem requires nonlinear time on a large class of algorithms, the same holds for the unify-deunify problem. Thus the linearity of single unifications does not give a complete picture of the time complexity of Prolog primitives. We discuss the methods for executing sequences of Datalog unifications used in Prolog interpreters and show that some of them require even quadratic time in the worst case. Complementing these results, we show that if the number of variables occurring in one clause is bounded by a constant, then the Datalog unify-deunify problem can be solved in linear time.A preliminary version of this paper appeared in the Third International Conference on Logic Programming, London, July 1986. This work was supported by the Academy of Finland and by TEKES.     

A generalized,one-way,stackless quicksort

This note generalizes the one-way, stackless quicksort of Huang and Knuth to work for any type of sort key. It thus proves that quicksort can run with minimal space inO(N logN) average time.On leave from FH Fulda, D-6400 Fulda (Germany).     

Formal neighbourhoods, combinatory Böhm trees, and untyped normalization by evaluation

We prove the correctness of an algorithm for normalizing untyped combinator terms by evaluation. The algorithm is written in the functional programming language Haskell, and we prove that it lazily computes the combinatory Böhm tree of the term. The notion of combinatory Böhm tree is analogous to the usual notion of Böhm tree for the untyped lambda calculus. It is defined operationally by repeated head reduction of terms to head normal forms. We use formal neighbourhoods to characterize finite, partial information about data, and define a Böhm tree as a filter of such formal neighbourhoods. We also define formal topology style denotational semantics of a fragment of Haskell following Martin-Löf, and let each closed program denote a filter of formal neighbourhoods. We prove that the denotation of the output of our algorithm is the Böhm tree of the input term. The key construction in the proof is a “glueing” relation between terms and semantic neighbourhoods which is defined by induction on the latter. This relation is related to the glueing relation which was earlier used for proving the correctness of normalization by evaluation algorithm for typed combinatory logic.     

Amortized analysis of some disk scheduling algorithms: SSTF,SCAN, andN-StepSCAN

The amortized analysis is a useful tool for analyzing the time-complexity of performing a sequence of operations. The disk scheduling problem involves a sequence of requests in general. In this paper, the performances of representative disk scheduling algorithms,SSTF, SCAN, andN-StepSCAN, are analyzed in the amortized sense. A lower bound of the amortized complexity for the disk scheduling problem is also derived. According to our analysis,SCAN is not only better thanSSTF andN-StepSCAN, but also an optimal algorithm. Various authors have studied the disk scheduling problem based on some probability models and concluded that the most acceptable performance is obtained fromSCAN. Our result therefore supports their conclusion.This research was supported by the National Science Council, Taiwan R. O. C. under contract: NSC80-0408-E009-11.     

Shape-Preserving Widths of Weighted Sobolev-Type Classes of Positive, Monotone, and Convex Functions on a Finite Interval

   Abstract. Let I be a finite interval, r∈ N and ρ(t)= dist {t, I} , t∈ I . Denote by Δ ^s ₊ L _q the subset of all functions y∈ L _q such that the s -difference Δ ^s _τ y(t) is nonnegative on I ,

From a Nonlinear, Nonconvex Variational Problem to a Linear, Convex Formulation

   Abstract. We propose a general approach to deal with nonlinear, nonconvex variational problems based on a reformulation of the problem resulting in an optimization problem with linear cost functional and convex constraints. As a first step we explicitly explore these ideas to some one-dimensional variational problems and obtain specific conclusions of an analytical and numerical nature.     

Points of local nonconvexity,clear visibility,and starshaped sets in Rd

Let S be a compact, connected, locally starshaped set in R^d, S not convex. For every point of local nonconvexity q of S, define A_q to be the subset of S from which q is clearly visible via S. Then ker S = {conv A_q: q lnc S}. Furthermore, if every d+1 points of local nonconvexity of S are clearly visible from a common d-dimensional subset of S, then dim ker S = d.     

Envelopes of Sets of Measures, Tightness, and Markov Control Processes

We introduce upper and lower envelopes for sets of measures on an arbitrary topological space, which are then used to give a tightness criterion. These concepts are applied to show the existence of optimal policies for a class of Markov control processes. Accepted 22 May 1998     

From a Nonlinear, Nonconvex Variational Problem to a Linear, Convex Formulation

Abstract. We propose a general approach to deal with nonlinear, nonconvex variational problems based on a reformulation of the problem resulting in an optimization problem with linear cost functional and convex constraints. As a first step we explicitly explore these ideas to some one-dimensional variational problems and obtain specific conclusions of an analytical and numerical nature.     

｛0,1,3｝问题摄动形式所对应的测度

给定实数λ,α以及Ｒ上（以λ,α为参数）的压缩自相似映射Ｓ１（ｘ）＝λｘ, Ｓ２（ｘ）＝ λｘ＋ａ, Ｓ３（ｘ）＝ λｘ＋３,记满足测度方程ｖ＝（１／３）∑ｉ＝１ｖｏＳｉ－１的唯一概率测度为ｕλ,α本文得到：（１）当固定 λ∈Ａ Ｅ（１／３, ２／５）时,则在 Ｌｅｂｅｓｇｕｅ测度意义下,对于 ａ．ｅ．的 ａ∈（０,１）,测度 ｕλ,α绝对连续,且存在平方可积密度．（２）若λ－１是 Ｐ．Ｖ．数,且 α是λ的有理系数多项式,则测度ｕλ,α是奇异测度．     

On systems of definitions,induction and recursion

Primitive recursion can be seen as the computational interpretation of induction through the Curry-Howard interpretation of propositions-as-types. In the present paper we discuss what happens if we apply this idea to possible non monotone inductive definitions. We start with a logical interpretation of a class of inductive definitions, thepartial inductive definitions. Then we internalise induction over such definitions as a rule of inference and consider a Curry-Howard interpretation of these definitions as type systems. As a basic example we discuss what meaning this interpretation gives to primitive recursion on a definition likeN=NN.     

Relaxed outer projections,weighted averages and convex feasibility

A new algorithmic scheme is proposed for finding a common point of finitely many closed convex sets. The scheme uses weighted averages (convex combinations) of relaxed projections onto approximating halfspaces. By varying the weights we generalize Cimmino's and Auslender's methods as well as more recent versions developed by Iusem & De Pierro and Aharoni & Censor. Our approach offers great computational flexibility and encompasses a wide variety of known algorithms as special instances. Also, since it is block-iterative, it lends itself to parallel processing.The research of the first author was partially supported by Ruhrgas under a NAVF grant.     

On specifications,subset types and interpretation of proposition in type theory

In this paper we discuss some practical aspects of using type theory as a programming and specification language, where the viewpoint is to use it not only as a basis for program synthesis but also as a programming language with a programming logic allowing us to do ordinary verification.The subset type has been added to type theory in order to avoid irrelevant information in programs. We give an example of a proof which illustrates the problems that may occur if the subset type is used in specifications when we have the standard interpretation of propositions as types. Harrop-formulas and Squash are then discussed as solutions to these problems. It is argued that they are not acceptable from a practical point of view.An extension of the theory to include the two new judgment forms:A is a proposition, andA is true, is then given and explained in terms of the old theory. The logical constants are no longer identified with the corresponding type theoretical constants, but propositions are interpreted as Gödel formulas, which allow us to introduce and justify logical rules similar to rules for classical logic. The interpretation is extended to include predicates defined by using reflections of the ordinary definition of Gödel formulas in a type of small propositions.The programming example is then revisited and stronger elimination rules are discussed.     

Local existence,lower mass bounds,and a new continuation criterion for the Landau equation

We consider the spatially inhomogeneous Landau equation with soft potentials. First, we establish the short-time existence of solutions, assuming the initial data has sufficient decay in the velocity variable and regularity (no decay assumptions are made in the spatial variable). Next, we show that the evolution instantaneously spreads mass throughout the domain. The resulting lower bounds are sub-Gaussian, which we show is optimal. The proof of mass-spreading is based on a stochastic process, and makes essential use of nonlocality. By combining this theorem with prior results, we derive two important applications: $C^{\infty }$-smoothing, even for initial data with vacuum regions, and a continuation criterion (the solution can be extended as long as the mass and energy densities stay bounded from above). This is the weakest condition known to prevent blow-up. In particular, it does not require a lower bound on the mass density or an upper bound on the entropy density.     

Filtering of Finite-State Time-Nonhomogeneous Markov Processes, a Direct Approach

A filtering equation is derived for P(x _t =x|y _s ,s∈[0,t]) for a continuous-time finite-state two-component time-nonhomogeneous cadlag Markov process z _t =(x _t ,y _t ) . The derivation is based on some new ideas in the filtering theory and does not require any knowledge of stochastic integration. Accepted 10 August 1999. Online publication 13 November 2000.     

On associators and the Grothendieck-Teichmuller group, I

We present a formalism within which the relationship (discovered by Drinfel'd in [Dr1], [Dr2]) between associators (for quasi-triangular quasi-Hopf algebras) and (a variant of) the Grothendieck-Teichmuller group becomes simple and natural, leading to a simplification of Drinfel'd's original work. In particular, we reprove that rational associators exist and can be constructed iteratively, though the proof itself still depends on the apriori knowledge that a not-necessarily-rational associator exists.     

A simple, accurate, geometrical approximation to the Keplerian motion

A new method which shows, simply and accurately, the planetary position as a geometrical point in the orbit as a function of time is presented. By comparison with the historical hypotheses of planetary motion, it is thus visually recognizable how such hypotheses, especially those propagated in the 17th century, approached the Keplerian motion geometrically by means of observations. The reason why such a mathematically accurate hypothesis as that presented here was not developed previously, say in the 17th century, was due mainly to the inaccurate values for the solar parallax involved in the observations of that time.     

Compactly Supported, Piecewise Affine Scaling Functions on Triangulations

The methods of using intertwining MRAs to find orthogonal scaling functions have previously been applied to one-dimensional MRAs and are here extended to two-dimensional bases. Two examples are constructed from MRAs consisting of continuous, compactly supported, piecewise affine functions of two variables. The resulting scaling functions can be conveniently restricted to compact domains. November 23, 1997. Date accepted: January 22, 1999.