On polymorphic types of untyped terms

Let S be a finite set of β normal closed terms and M and N a pair of β normal, η   distinct, closed terms. Then there exist polymorphic types a,b$a,b$ such that every member of S can be typed as a, and M and N have η expansions which can be typed as b; where, in the resulting typings, the members of S can be simultaneously consistently identified, and the η expansions of M and N are βη inconsistent (no model with more than one element of any type). A similar result holds in the presence of surjective pairing.     

Recursion-free modular arithmetic in the lambda-calculus

We investigate encodings for modular arithmetic in the lambda-calculus. There are two approaches: adapting well-known numeral systems, and building a new one. This paper focuses on providing original techniques to encode modular arithmetic directly. We present a modular arithmetic numeral system complete with multiplication and an implementation of the Chinese remainder theorem, all without recursion i.e., without using fixed-point operators.     

Performance of lazy combinator graph reduction

The performance of program-derived combinator graph reduction is known to be superior to that of graph reduction based on a fixed set of standard combinators. The major advantage of program-derived combinator reduction is that it uses less transient store than standard combinator reduction. We show on what activities a combinator reduction algorithm spends its execution time. Based on this analysis we show that it depends to a large extent on the application how much faster a program will run if program-derived combinators are used instead of standard combinators. The analysis is based on experimental evidence obtained from a small bench-mark of medium-size functional programs. Performance gains of up to 11 x are reported for target architectures on which each memory reference consumes one unit of time. The results are valid for implementations of combinator graph reduction that use binary graphs.     

On the correctness of the Krivine machine

We provide a short proof of the correctness of the Krivine machine by showing how it simulates weak head reduction.     

On the choice of spatial and categorical scale in remote sensing land cover classification

Our interest in this paper is on the choice of spatial and categorical scale, and their interaction, in creating classifications of land cover from remotely sensed measurements. We note that in discussing categorical scale, the concept of spatial scale naturally arises, and in discussing spatial scale, the issue of aggregation of measurements must be considered. Therefore, and working towards an ultimate goal of producing multiscale, multigranular characterizations of land cover, we address here successively and in a cumulative fashion the topics of (1) aggregation of measurements across multiple scales, (2) adaptive choice of spatial scale, and (3) adaptive choice of categorical scale jointly with spatial scale. We show that the use of statistical finite mixture models with groups of original pixel-scale measurements, at successive spatial scales, offers improved pixel-wise classification accuracy as compared to the commonly used technique of label aggregation. We then show how a statistical model selection strategy may be used with the finite mixture models to provide a data-adaptive choice of spatial scale, varying by location (i.e., multiscale), from which classifications at least as accurate as those of any single spatial scale may be achieved. Finally, we extend this paradigm to allow for jointly adaptive selection of spatial and categorical scale. Our emphasis throughout is on the empirical quantification of the role of the various elements above, and a comparison of their performance with standard methods, using various artificial landscapes. The methods proposed in this paper should be useful for a variety of scale-related land cover classification tasks.     

Cooperation of categorical and behavioral learning in a practical solution to the abstraction problem

Real robots should be able to adapt autonomously to various environments in order to go on executing their tasks without breaking down. They achieve this by learning how to abstract only useful information from a huge amount of information in the environment while executing their tasks. This paper proposes a new architecture which performs categorical learning and behavioral learning in parallel with task execution. We call the architectureSituation Transition Network System (STNS). In categorical learning, it makes a flexible state representation and modifies it according to the results of behaviors. Behavioral learning is reinforcement learning on the state representation. Simulation results have shown that this architecture is able to learn efficiently and adapt to unexpected changes of the environment autonomously. Atsushi Ueno, Ph.D.: He is a research associate in the Artificial Intelligence Laboratory at the Graduate School of Information Science at the Nara Institute of Science and Technology (NAIST). He received the B.E., the M.E., and the Ph.D. degrees in aeronautics and astronautics from the University of Tokyo in 1991, 1993, and 1997 respectively. His research interest is robot learning and autonomous systems. He is a member of Japan Association for Artificial Intelligence (JSAI). Hideaki Takeda, Ph.D.: He is an associate professor in the Artificial Intelligence Laboratory at the Graduate School of Information Science at the Nara Institute of Science and Technology (NAIST). He received his Ph.D. in precision machinery engineering from the University of Tokyo in 1991. He has conducted research on a theory of intelligent computer-aided design systems, in particular experimental study and logical formalization of engineering design. He is also interested in multiagent architectures and ontologies for knowledge base systems.     

On the elimination of quantifier-free cuts

When investigating the complexity of cut-elimination in first-order logic, a natural subproblem is the elimination of quantifier-free cuts. So far, the problem has only been considered in the context of general cut-elimination, and the upper bounds that have been obtained are essentially double exponential. In this note, we observe that a method due to Dale Miller can be applied to obtain an exponential upper bound.     

Proofs-as-Programs as a Framework for the Design of an Analogy-Based ML Editor

C ^Y NTHIA is a transformation-based editor for a functional subset of ML that lies somewhere between a structure editor and a framework for formal program development. Users construct programs from existing code by applying editing commands that make a semantic analysis of the program's behaviour, e.g., whether it is terminating. All analysis is done using the Oyster system, which is an implementation of proofs-as-programs. We concentrate on identifying analyses that can be done fully automatically (e.g., using a decision procedure) and hence can be hidden from the user. As a result, C ^Y NTHIA represents progress towards a goal of program editors that make an intelligent analysis of their code, but in a way that requires no extra input from the programmer. Received October 2000 / Accepted in revised form April 2001     

Agent's actions as a classification criteria for the state space in a learning from rewards system

We focus in this paper on the problem of learning an autonomous agent's policy when the state space is very large and the set of actions available is comparatively short. To this end, we use a non-parametric decision rule (concretely, a nearest-neighbour strategy) in order to cluster the state space by means of the action that leads to a successful situation. Using an exploration strategy to avoid greedy behaviour, the agent builds clusters of positively-classified states through trial and error learning. In this paper, we implement a 3D synthetic agent which plays an ‘avoid the asteroid’ game that suits our assumptions. Using as the state space a feature vector space extracted from a visual navigation system, we test two exploration strategies using the trial and error learning method. This experiment shows that the agent is a good classifier over the state space, and will therefore show good behaviour in its synthetic world.     

On the possibilities of (pseudo-) software cloning from external interactions

This paper discusses some initial investigations into the application of genetic programming technology as a vehicle for re-examining some existing approaches within the software life-cycle. Specifically, it outlines a new direction in production techniques—software cloning from executable specifications or source code. It explores the possibility and advantages of producing a system from its external interactions. To allow this production to be automatic, the system assumes that it can view (and potentially manipulate) these external interactions of the original system; and hence it assumes the existence of either an executable specification or the source code—an object to assist in the generation of the external interactions; i.e. the system is treated as a black-box. Although the generation and application of software clones is relatively unexplored, it is believed that this is a fundamental technology that can have many different applications within a software engineering environment. For example, software clones could be used in: complexity measurement, software testing and software fault tolerance. Clearly, for these clones to be usable, their production needs to be automated. An interesting approach to this automatic production or generation problem is the application of evolutionary-based Genetic Programming (GP). Using the paradigms of best fit, selection, crossover and mutation, a number of clones, satisfying specific requirements, can be automatically generated. In general, GP is a flexible and powerful algorithm suitable for solving a variety of different problems. This paper presents the results of studies that have been conducted in order to answer questions related to feasibility of using GP for clone generation: what features of GP are important? What works and what does not? How can the GP be “tuned” for the problem? The results have been used to draw a set of suggestions and conclusions that indicate possible usability of GP-based approach to automatic generation of clones.     

The limited value of cophenetic correlation as a clustering criterion

A common procedure for evaluating hierarchical cluster techniques is to compare the input data, in terms of for example a matrix of similarities or dissimilarities, with the output hierarchy expressed in matrix form. If an ordinary product-moment correlation is used for this comparison, the technique is known as that of cophenetic correlations, frequently used by numerical taxonomists. A high correlation between the input similarities and the output dendrogram has been regarded as a criterion of a successful classification. This paper contains a Monte Carlo study of the characteristics of the cophenetic correlation and a related measure of agreement which have been both interpreted in terms of generalized variance for some different hierarchical cluster algorithms. The generalized variance criterion chosen for this study is Wilk's lambda, whose sampling distribution under the null hypothesis of identical group centroids is used in this context to define the degree of separation between clusters. Thus, a probabilistic approach is introduced into the evaluation procedure. With the above definition of presence of clusters, use of the cophenetic correlation and related measures of agreement as criteria of goodness-of-fit is shown to be quite misleading in most cases. This is due to their large variability for low separation of clusters.     

The development of the HiPE system: design and experience report

The concurrent functional programming language Erlang has been designed to ease the development of large-scale distributed soft real-time control applications. So far, it has been used quite successfully in industry, both within Ericsson Telecom, where it was designed and developed, and by other companies. This declarative language success-story has taken place despite the fact that Erlang implementations are slow compared with implementations of other functional languages. Wanting to improve the performance aspects of publicly available Erlang implementations, which are based on emulators, we embarked on a project called HiPE (High-Performance Erlang) whose aim has been to develop an efficient just-in-time native code compiler for Erlang (called the HiPE system). Since its start in 1996, the system has gone through various (re-)design phases, partly due to implementation choices that did not turn out to be as promising as they appeared on paper, but mainly due to changes in Ericssons Erlang system upon which the HiPE system is built. In this article, we describe how the HiPE system was developed, what it currently looks like, and its current performance. We critically examine design decisions that we took, and the main lessons learnt from implementing them. Finally, we also report on our experiences from trying to keep up with the concurrent development of Ericssons base Erlang system. As such, this article both documents the HiPE system and can serve as possible guidance to anyone wishing to attempt a similar feat.     

On the complexity of interval scheduling with a resource constraint

We consider a scheduling problem where jobs have to be carried out by parallel identical machines. The attributes of a job j are: a fixed start time s_j, a fixed finish time f_j, and a resource requirement r_j. Every machine owns R units of a renewable resource necessary to carry out jobs. A machine can process more than one job at a time, provided the resource consumption does not exceed R. The jobs must be processed in a non-preemptive way. Within this setting, the problem is to decide whether a feasible schedule for all jobs exists or not.We discuss such a decision problem and prove that it is strongly NP-complete even when the number of resources are fixed to any value R≥2. Moreover, we suggest an implicit enumeration algorithm which has O(nlogn) time complexity in the number n of jobs when the number m of machines and the number R of resources per machine are fixed.The role of storage layout and preemption are also discussed.     

On one numerical method for solving some self-similarityproblems of gas-dynamics on a multiprocessor

In this paper we consider mathematical models of some problems of natural science, for example, self-similarity problems of gas-dynamics giving rise to boundary problems of first order ordinary differential equations (ODE) with one parameter. The boundary problems of first order ODE with one parameter are considered in [1, 2], where iterative methods based on the implementation of Newton's Method, are presented. Next, an iterative method for solving the boundary value problem of the first order system of ODE with one parameter on a multiprocessor type SIMD [3] is shown. The convergence of this process is proved and the speed of convergence is estimated. The feasibility of this method is illustrated for the one dimensional instability movement of gas arising from the movement of the piston in presence of a volume source (volume channel) of mass, impulse and energy in gas. Finally the results are given.     

On the impact of adaptive test question selection for learning efficiency

In this paper we present a method for adaptive selection of test questions according to the individual needs of students within a web-based educational system. It functions as a combination of three particular methods. The first method is based on the course structure and focuses on the selection of the most appropriate topic for learning. The second uses Item Response Theory to select the k-best questions with adequate difficulty for a particular learner. The last is based on the usage history and prioritizes questions according to specific strategies, e.g. to filter out the questions that were recently asked. We describe how these methods evaluate user answers to gather information concerning their characteristics for a more precise selection of further questions. We describe an evaluation of the impact of a proposed method through two different types of experiments in the domain of learning programming, which both showed that our method for adaptive test question selection increases the overall learning outcome, especially for lower than average performing students.     

On a system of first-order quasi-variational inequalities connected with the optimal switching problem

In this paper we prove the existence of the maximum bounded Lipschitz continuous solution to a system of first-order quasi-variational inequalities. The method is to discretize by an Euler scheme the characteristic lines of the differential operator appearing in the system and to solve by iteration the corresponding approximate problem. The solution is interpreted as the value function of a deterministic optimal switching problem.