Searching minimax game trees under memory space constraint

Games such as CHESS, GO and OTHELLO can be represented by minimax game trees. Among various search procedures to solve such game trees,- and SSS^* are perhaps most well known. Although it is proved that SSS^* explores only a subset of the nodes explored by-, - is commonly believed to be faster in real applications, since it requires very little memory space and hence its storage management cost is low. Contrary to this folklore, however, this paper reports, using the OTHELLO game as an example, that SSS^* is much faster than-. It is also demonstrated that SSS^* can be modified to make the required memory space controllable to some extent, while retaining the high efficiency of the original SSS^*.This research was partially supported by the Ministry of Education, Science and Culture of Japan, under a Scientific Grant-in-Aid.     

Asymptotic Stability of Nonlinear Pulse Systems

A nonlinear pulse system and its equivalent nonlinear system derived through substitution of the pulse element by a static characteristic are studied. For high pulsation frequency, the equilibrium state of the pulse system is shown to be asymptotically stable if the equivalent linearized system is asymptotically stable.     

Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems

In recent years, constraint satisfaction techniques have been successfully applied to disjunctive scheduling problems, i.e., scheduling problems where each resource can execute at most one activity at a time. Less significant and less generally applicable results have been obtained in the area of cumulative scheduling. Multiple constraint propagation algorithms have been developed for cumulative resources but they tend to be less uniformly effective than their disjunctive counterparts. Different problems in the cumulative scheduling class seem to have different characteristics that make them either easy or hard to solve with a given technique. The aim of this paper is to investigate one particular dimension along which problems differ. Within the cumulative scheduling class, we distinguish between highly disjunctive and highly cumulative problems: a problem is highly disjunctive when many pairs of activities cannot execute in parallel, e.g., because many activities require more than half of the capacity of a resource; on the contrary, a problem is highly cumulative if many activities can effectively execute in parallel. New constraint propagation and problem decomposition techniques are introduced with this distinction in mind. This includes an O(n²) edge-finding algorithm for cumulative resources (where n is the number of activities requiring the same resource) and a problem decomposition scheme which applies well to highly disjunctive project scheduling problems. Experimental results confirm that the impact of these techniques varies from highly disjunctive to highly cumulative problems. In the end, we also propose a refined version of the edge-finding algorithm for cumulative resources which, despite its worst case complexity in O(n³) , performs very well on highly cumulative instances.     

The Application of Workflow Technology in Semantic B2B Integration

Workflow Management Systems (WFMSs) are often used in context of B2B integration as a base technology to implement business-to-business (B2B) integration processes across enterprises. In this context the notion of distributed inter-organizational workflows is introduced to indicate the collaboration of enterprises on a process level. This notion requires a thorough examination presented in this article since WFMSs were not designed with inter-enterprise distribution as one of the design goals. At a closer look, the proposed use of WFMSs in context of B2B integration is often very naïve and inappropriate. Consequently it does not address the real requirements found in enterprises. Enterprises do not share common workflow definitions, let alone common workflow instance execution state and have no intent to do so due to competitive knowledge protection. Furthermore, trading partner specific business rules within enterprises are not accounted for leading to an unwanted explosion of workflow definitions. This article clarifies the notion of distributed inter-organizational workflows as well as private and public processes. Based on this definition, the appropriate use of WFMSs is shown in context of an overall B2B integration solution that allows enterprises to protect their competitive knowledge while participating in B2B integration.     

Dimensional properties of graphs and digital spaces

Many applications of digital image processing now deal with three- and higher-dimensional images. One way to represent n-dimensional digital images is to use the specialization graphs of subspaces of the Alexandroff topological space ⁿ (where denotes the integers with the Khalimsky line topology). In this paper the dimension of any such graph is defined in three ways, and the equivalence of the three definitions is established. Two of the definitions have a geometric basis and are closely related to the topological definition of inductive dimension; the third extends the Alexandroff dimension to graphs. Diagrams are given of graphs that are dimensionally correct discrete models of Euclidean spaces, n-dimensional spheres, a projective plane and a torus. New characterizations of n-dimensional (digital) surfaces are presented. Finally, the local structure of the space ⁿ is analyzed, and it is shown that ⁿ is an n-dimensional surface for all n1.     

On input semigroups of automata

In this paper, we consider the problem of what topological semigroups can serve as input semigroups of what (topological) automata. A semigroup is said to be admissible if it serves as an input semigroup of a non-trivial strongly connected automaton that has a distinguishable state (see Definition 2). For the discrete or the compact case, the class of all the admissible semigroups is fully characterized: a discrete or compact topological semigroup (I, m) is admissible if and only if there exists a closed congruence relationR such that the quotient semigroup (I/R, m _R ) is non-trivial, right simple, and left unital. This work stems from Weeg's [10], who considered a similar problem in the discrete case.In the last section of the paper, a conjecture of Weeg [10, p. 264] is resolved in the negative.     

Information and pragmatic value-adding: Language games and information science

This paper discusses terms which are of mutual importance to the fields of information science and computer science. Specifically we discuss the notions of information and knowledge: their interrelationships as well as their differences, and the concept of value-adding. Concrete examples are used in the discussion.Rainer Kuhlen is professor of Information Science at the University of Konstanz.     

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.     

A multiprocessor working as a Fault-Tolerant cellular automaton

A memory-coupled multiprocessor—well suited to bit-wise operation—can be utilized to operate as a 1024 items cellular processing unit. Each processor is working on 32 bits and 32 such processors are combined to a multiprocessor. The information is stored in vertical direction, as it is defined and described in earlier papers [1] on vertical processing. The two-dimensional array (32 times 32 bits) is composed of the 32 bit-machine-words of the coupled processors on the one hand and of 32 processors in nearest-neighbour-topology on the other hand. The bit-wise cellular operation at one of the 1024 points is realized by the program of the processor—possibly assisted by appropriate microprogam sequences.Dedicated to Professor Willard L. Miranker on the occasion of his 60th birthday     

Characterizations of reduction classes modulo oracle conditions

It is known that nondeterministic polynomial time truth-table reducibility is exactly the same as nondeterministic polynomial time Turing reducibility. Here we study the standard nondeterministic reducibilities (conjunctive, bounded truth-table, bounded positive truth-table, and many-one) and show that each is a restriction of nondeterministic polynomial time Turing reducibility corresponding to acceptance modulo a set of oracle conditions. Then we show that the reduction classes of these reducibilities are classes of formal languages and as such have language theoretic characterization theorems. The same program is carried out for polynomial space.This research was supported in part by the National Science Foundation under Grants MCS77-23493, MSC80-11979, MCS81-20263, and MCS83-12472. The work of the second author was also supported by the United States-Israel Educational Foundation (Fulbright Award).     

Quantitative Characterization of Event Streams in Analysis of Hard Real-Time Applications

Many real-time embedded systems process event streams that are composed of a finite number of different event types. Each different event type on the stream would typically impose a different workload to the system, and thus the knowledge of possible correlations and dependencies between the different event types could be exploited to get tighter analytic performance bounds of the complete system. We propose an abstract stream model to characterize such an event stream. The model captures the needed information of all possible traces of a class of event streams. Hence, it can be used to obtain hard bounded worst-case and best-case analysis results of a system. We show how the proposed abstract stream model can be obtained from a concrete stream specification, and how it can be used for performance analysis. The applicability of our approach and its advantages over traditional worst-case performance analysis are shown in a case study of a multimedia application.Ernesto Wandeler is a Ph.D. student at the Computer Engineering and Networks Laboratory of the Swiss Federal Institute of Technology, Zurich. His research interests include models, methods and tools for system-level performance analysis of real-time embedded systems. He holds a Dipl. El.-Ing. degree from ETH Zurich. In 2003, he received the Willi Studer Price and the ETH Medal, both from the Swiss Federal Institute of Technology, Zurich. He is a student member of the IEEE and the ACM.Alexander Maxiaguine is a Ph.D. student at the Computer Engineering and Networks Laboratory of the Swiss Federal Institute of Technology, Zurich. His research interests include models and methods for system-level performance analysis and scheduling of embedded multiprocessor architectures, especially for real-time multimedia applications. Maxiaguine has an M.S. in electrical engineering from the Moscow Technical University of Communications and Informatics. He is a member of the IEEE and the ACM.Lothar Thiele is a full professor of computer engineering at the Swiss Federal Institute of Technology, Zurich. His research interests include models, methods and software tools for the design of embedded systems, embedded software and bioinspired optimization techniques. In 1986 he received the Dissertation Award of the Technical University of Munich, in 1987, the Outstanding Young Author Award of the IEEE Circuits and Systems Society, in 1988, the Browder J. Thompson Memorial Award of the IEEE, and in 2000–2001, the IBM Faculty Partnership Award. In 2004, he joined the German Academy of Natural Scientists Leopoldina.     

Shape optimization using adaptive high-order finite elements

In recent years, the state of the art in shape optimization has advanced due to new approaches proposed by various researchers. A fundamental difficulty in shape optimization is that the original finite element mesh may become invalid during large shape changes. Automatic remeshing and velocity field approaches are most commonly used for conventionalh-type finite element analysis to address this problem.In this paper, we describe a different approach to shape optimization based on the use of high-orderp-type finite elements tightly coupled to a parameterized computational geometry module. The advantages of this approach are as follows.Accurate results can be obtained with much fewer finite elements, so large shape changes are possible without remeshing.Automatic adaptive analysis may be performed so that accurate results are achieved at each step of the optimization process.Since the elements derive their geometric mapping from the underlying geometry, the fundamental equivalent of velocity field element shape updating may be readily achieved.Results are presented for sizing and shape optimization with this approach and contrasted with previous results from the literature.     

Behaviourally constrained contact force optimization

In this paper, the problem of optimizing the contact force distribution between a rigid obstacle and an elastic discrete body is considered. The initial distances between the bodies are taken as design variables and the equilibrium total potential energy as the cost function.A standard result is now that if an isoperimetric design constraint prescribing the gap volume is included, the resulting distribution of contact forces is constant; a desirable property. This article includes an investigation of the outcome when the design constraint is interchanged with general behavioural constraints on the contact forces.Special cases are considered: on one hand, if the sum of all contact forces is prescribed, constant interference is a result, and on the other hand, if the value of each contact force is bounded, the optimization gives constant contact forces.     

On efficient deterministic simulation of turing machine computations below logaspace

It is shown that a bounded language accepted by a nondeterministic Turing machine in spaceS(n o(logn) can be accepted by a deterministic Turing machine in space MAX {(s(nn))², logn}. This can be interpreted as extending Savitch's algorithm below logspace. Results of Alt can be used to show that in the general case the indicated space bound cannot be improved. The result can also be interpreted as a sharpening in the special case of bounded languages of the results of Monien and Sudborough.     

Unification in partially commutative semigroups

Unification algorithms have been constructed for semigroups and commutative semigroups. This paper considers the intermediate case of partially commutative semigroups. We introduce classesN and of such semigroups and justify their use. We present an equation-solving algorithm for any member of the classN. This algorithm is relative to having an algorithm to determine all non-negative solutions of a certain class of diophantine equations of degree 2 which we call -equations. The difficulties arising when attempting to solve equations in members of the class are discussed, and we present arguments that strongly suggest that unification in these semigroups is undecidable.     

Quantum monadology: A world model to interpret quantum mechanics and relativity

In order to give a new insight to fundamental problems of quantum mechanics, relativity and mind, we propose a world model suggested from the monadology of Leibniz. The world is assumed to consist of monads which have their individuality and whose primary attribute is a space-time frame and not a position in spacetime. Each monad has freedom to change its frame. Accompanying this change, the world time is put forward, and the world state jumps off the unitary evolution. This model explains not only the measurement process of quantum mechanics but also the passing now and the origin of free will.     

Real-time Collision-free Path Planning of Robot Manipulators using Neural Network Approaches

In this paper, a novel neural network approach to real-time collision-free path planning of robot manipulators in a nonstationary environment is proposed, which is based on a biologically inspired neural network model for dynamic trajectory generation of a point mobile robot. The state space of the proposed neural network is the joint space of the robot manipulators, where the dynamics of each neuron is characterized by a shunting equation or an additive equation. The real-time robot path is planned through the varying neural activity landscape that represents the dynamic environment. The proposed model for robot path planning with safety consideration is capable of planning a real-time comfortable path without suffering from the too close nor too far problems. The model algorithm is computationally efficient. The computational complexity is linearly dependent on the neural network size. The effectiveness and efficiency are demonstrated through simulation studies.     

An Entropy Theoretic Inversion Formula for the Distribution of Proper Values of a Compact Positive Operator

A formula for estimating -entropy of a compact positive operator in terms of the distribution of proper values of such an operator was given by Prosser and Root. In this paper, an inversion formula for estimating the distribution of proper values of a compact positive operator in terms of -entropy of such an operator is given.     

Trainable Articulatory Control Models for Visual Speech Synthesis

This paper deals with the problem of modelling the dynamics of articulation for a parameterised talking head based on phonetic input. Four different models are implemented and trained to reproduce the articulatory patterns of a real speaker, based on a corpus of optical measurements. Two of the models, (Cohen-Massaro and Öhman) are based on coarticulation models from speech production theory and two are based on artificial neural networks, one of which is specially intended for streaming real-time applications. The different models are evaluated through comparison between predicted and measured trajectories, which shows that the Cohen-Massaro model produces trajectories that best matches the measurements. A perceptual intelligibility experiment is also carried out, where the four data-driven models are compared against a rule-based model as well as an audio-alone condition. Results show that all models give significantly increased speech intelligibility over the audio-alone case, with the rule-based model yielding highest intelligibility score.