The historical workstation project

Since 1978 research in the development of software dedicated to the specific problems of historical research has been undertaken at the Max-Planck-Institute für Geschichte in Göttingen. From a background of practical experiences during these years, a concept of what an appropriate workstation for an historian would be has been derived. It stresses the necessity of three components: (a) software, derived from a detailed analysis of what differentiates information contained in historical sources from such present in current material, (b) databases which are as easily available as printed books and (c) knowledge bases which allow software and data bases to draw upon the information contained in historical reference works. A loose network of European research projects, dedicated to the realization of such a setup, is described.Manfred Thaller has a Ph.D. (1975) in Modern and Medieval History and held a post-doctoral fellowship in sociology at the Institute for Advanced Studies (Vienna). Since 1978 he has been at the Max-Planck-Institute for History, where he is a research fellow for Historical Information Science.     

Stochastic structural topology optimization: discretization and penalty function approach

We consider structural topology optimization problems, including unilateral constraints arising from, for example, non-penetration conditions in contact mechanics or non-compression conditions for elastic ropes. To construct more realistic models and to circumvent possible failures or inefficient behaviour of optimal structures, we allow parameters (for example, loads) defining the problem to be stochastic. The resulting non-smooth stochastic optimization problem is an instance of stochastic mathematical programs with equilibrium constraints (MPEC), or stochastic bilevel programs. We propose a solution scheme based first on the approximation of the given topology optimization problem by a sequence of simpler sizing optimization problems, and second on approximating the probability measure in the latter problems. For stress-constrained weight-minimization problems, an alternative to -perturbation based on a new penalty function is proposed.     

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.     

Stable relaxations of stochastic stress-constrained weight minimization problems

The problem of finding a truss of minimal weight subject to stress constraints and stochastic loading conditions is considered. We demonstrate that this problem is ill-posed by showing that the optimal solutions change discontinuously as small changes in the modelling of uncertainty are introduced. We propose a relaxation of this problem that is stable with respect to such errors. We establish a classic -perturbation result for the relaxed problem, and propose a solution scheme based on discretizations of the probability measure. Using Chebyshevs inequality we give an a priori estimation of the probability of stress constraint violations in terms of the relaxation parameter. The convergence of the relaxed optimal designs towards the original (non-relaxed) optimal designs, as the relaxation parameter decreases to zero, is established.     

A Problem of Control of Random Processes

A control problem for a random process depending additively on the fractional Brownian motion with the Hurst parameter H (1/2, 1) is analyzed.     

From Pre-Historic to Post-Modern Symbolic Model Checking

Symbolic model checking, which enables the automatic verification of large systems, proceeds by calculating expressions that represent state sets. Traditionally, symbolic model-checking tools are based on backward state traversal; their basic operation is the function pre, which, given a set of states, returns the set of all predecessor states. This is because specifiers usually employ formalisms with future-time modalities, which are naturally evaluated by iterating applications of pre. It has been shown experimentally that symbolic model checking can perform significantly better if it is based, instead, on forward state traversal; in this case, the basic operation is the function post, which, given a set of states, returns the set of all successor states. This is because forward state traversal can ensure that only parts of the state space that are reachable from an initial state and relevant for the satisfaction or violation of the specification are explored; that is, errors can be detected as soon as possible.In this paper, we investigate which specifications can be checked by symbolic forward state traversal. We formulate the problems of symbolic backward and forward model checking by means of two -calculi. The pre- calculus is based on the pre operation, and the post- calculus is based on the post operation. These two -calculi induce query logics, which augment fixpoint expressions with a boolean emptiness query. Using query logics, we are able to relate and compare the symbolic backward and forward approaches. In particular, we prove that all -regular (linear-time) specifications can be expressed as post- queries, and therefore checked using symbolic forward state traversal. On the other hand, we show that there are simple branching-time specifications that cannot be checked in this way.     

T-Efficient Calculation of the ε-Solutions to Problems of Calculus and Applied Mathematics. II

An approach to the construction of algorithms that are efficient for complexity and that calculate -solutions to computation and applied mathematics problems is described in the first part of the present paper. This approach is applied for creation of T-efficient algorithms used to solve some classes of nonlinear integral equations, ordinary differential equations, and global optimization.     

Reasoning about action and change

Reasoning about change is a central issue in research on human and robot planning. We study an approach to reasoning about action and change in a dynamic logic setting and provide a solution to problems which are related to the Frame problem. Unlike most work on the frame problem the logic described in this paper is monotonic. It (implicitly) allows for the occurrence of actions of multiple agents by introducing non-stationary notions of waiting and test. The need to state a large number of frame axioms is alleviated by introducing a concept of chronological preservation to dynamic logic. As a side effect, this concept permits the encoding of temporal properties in a natural way. We compare the relative merits of our approach and non-monotonic approaches as regards different aspects of the frame problem. Technically, we show that the resulting extended systems of propositional dynamic logic preserve (weak) completeness, finite model property and decidability.     

Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds

We consider the following problem: given a robot system, find a minimal-time trajectory that goes from a start state to a goal state while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. In [1] we developed a provably good approximation algorithm for the minimum-time trajectory problem for a robot system with decoupled dynamics bounds (e.g., a point robot in ³). This algorithm differs from previous work in three ways. It is possible (1) to bound the goodness of the approximation by an error term; (2) to bound the computational complexity of our algorithm polynomially; and (3) to express the complexity as a polynomial function of the error term. Hence, given the geometric obstacles, dynamics bounds, and the error term, the algorithm returns a solution that is-close to optimal and requires only a polynomial (in (1/)) amount of time.We extend the results of [1] in two ways. First, we modify it to halve the exponent in the polynomial bounds from 6d to 3d, so that the new algorithm isO(c ^d N 1/)^3d ), whereN is the geometric complexity of the obstacles andc is a robot-dependent constant. Second, the new algorithm finds a trajectory that matches the optimal in time with an factor sacrificed in the obstacle-avoidance safety margin. Similar results hold for polyhedral Cartesian manipulators in polyhedral environments.The new results indicate that an implementation of the algorithm could be reasonable, and a preliminary implementation has been done for the planar case.This paper describes research done at the Computer Science Robotics Laboratory at Cornell University. Support for our robotics research there is provided in part by the National Science Foundation under Grant Nos. IRI-8802390 and IRI-9000532, by a Presidential Young Investigator award, and in part by the Mathematical Sciences Institute, Intel Corporation, and AT&T Bell Laboratories.     

A predicate transformer for the progress property ‘to-always’

The temporal property to-always has been proposed for specifying progress properties of concurrent programs. Although the to-always properties are a subset of the leads-to properties for a given program, to-always has more convenient proof rules and in some cases more accurately describes the desired system behavior. In this paper, we give a predicate transformerwta, derive some of its properties, and use it to define to-always. Proof rules for to-always are derived from the properties ofwta. We conclude by briefly describing two application areas, nondeterministic data flow networks and self-stabilizing systems where to-always properties are useful.     

Verifying programs in the calculus of inductive constructions

This paper deals with a particular approach to the verification of functional programs. A specification of a program can be represented by a logical formula [Con86, NPS90]. In a constructive framework, developing a program then corresponds to proving this formula. Given a specification and a program, we focus on reconstructing a proof of the specification whose algorithmic contents corresponds to the given program. The best we can hope is to generate proof obligations on atomic parts of the program corresponding to logical properties to be verified. First, this paper studies a weak extraction of a program from a proof that keeps track of intermediate specifications. From such a program, we prove the determinism of retrieving proof obligations. Then, heuristic methods are proposed for retrieving the proof from a natural program containing only partial annotations. Finally, the implementation of this method as a tactic of theCoq proof assistant is presented.This research was partly supported by ESPRIT Basic Research Action Types for Proofs and Programs and by Programme de Recherche Coordonnes and CNRS Groupement de Recherche Programmation.     

A Mathematical Analysis of Pānini’s <Emphasis Type="Italic">Śivasūtras</Emphasis>

In Pninis grammar of Sanskrit one finds the ivastras, a table which defines the natural classes of phonological segments in Sanskrit by intervals. We present a formal argument which shows that, using his representation method, Pninis way of ordering the phonological segments to represent the natural classes is optimal. The argument is based on a strictly set-theoretical point of view depending only on the set of natural classes and does not explicitly take into account the phonological features of the segments, which are, however, implicitly given in the way a language clusters its phonological inventory. The key idea is to link the graph of the Hasse-diagram of the set of natural classes closed under intersection to ivastra-style representations of the classes. Moreover, the argument is so general that it allows one to decide for each set of sets whether it can be represented with Pninis method. Actually, Pnini had to modify the set of natural classes to define it by the ivastras (the segment h plays a special role). We show that this modification was necessary and, in fact, the best possible modification. We discuss how every set of classes can be modified in such a way that it can be defined in a ivastra-style representation.¹     

AI & Society and society

This article looks at the broadest implications of public acceptance of AI. A distinction is drawn between conscious belief in a technology, and organic belief where the technology is incorporated into an unconscious world model. The extent to which we feel threatened by AI's apparent denial of spirit is considered, along with a discussion of how people react to this threat. It is proposed that organic acceptance of AI models would lead to a rebirth of popular spiritual concepts as paradoxical as the New Age ideas that have their roots in the theories of physics. Finally the relevance of this speculation is discussed in terms of how it could impinge upon public acceptability of AI technology.     

Fast Online Q(λ)

Q()-learning uses TD()-methods to accelerate Q-learning. The update complexity of previous online Q() implementations based on lookup tables is bounded by the size of the state/action space. Our faster algorithm's update complexity is bounded by the number of actions. The method is based on the observation that Q-value updates may be postponed until they are needed.     

More Church–Rosser Proofs

The proofs of the Church–Rosser theorems for , , and reduction in untyped -calculus are formalized in Isabelle/HOL, an implementation of Higher Order Logic in the generic theorem prover Isabelle. For -reduction, both the standard proof and Takahashi's are given and compared. All proofs are based on a general theory of commutating relations that supports an almost geometric style of reasoning about confluence diagrams.     

CoABS Grid Scalability Experiments

The CoABS Grid is middleware that integrates heterogeneous agent-based, object-based, and legacy systems. It includes a method-based application programming interface to register agents, advertise agent capabilities, discover agents based on their capabilities, and send messages between agents. Agent registration and discovery are reliant on one or more lookup services. The experiments discussed in this paper investigate how timing of sequential agent registration and lookup varies as the total number of registered agents increases. No degradation in performance was observed in experiments with up to 10,000 agents for lookup. Minimal degradation in registration time was observed as the number of registered agents increased. Further experiments are planned.     

Intelligent Manufacturing:Present State and Future Trends

AI methods are introduced to an increasing extent in the field of CIM and robotics. This development results in intelligent CIM components – ICAD, ICAP, ICAM, ICAQ – and in intelligent manufacturing systems (IMS) as well as in intelligent robots. This new philosophy requires a lot of prerequisites and research. ICIM or IMS is partially introduced in industry but mainly for large companies. AI as knowledge based and expert systems is ready to be introduced in an efficient way in CIM components. Intelligent, mobile robots as integrated parts of CIM and IMS are ready to be used in factory automation. One of the next steps could be the introduction of Multi-Agent and/or holonic systems. In this contribution the history and the present state of flexible manufacturing, with special emphasis on robotics, are described and further trends in development – Multi Agent Systems – are discussed mainly from the viewpoint of SMEs.     

The Wearable Motherboard™: The first generation of adaptive and responsive textile structures (ARTS) for medical applications

Virtual reality (VR) has been making inroads into medicine in a broad spectrum of applications, including medical education, surgical training, telemedicine, surgery and the treatment of phobias and eating disorders. The extensive and innovative applications of VR in medicine, made possible by the rapid advancements in information technology, have been driven by the need to reduce the cost of healthcare while enhancing the quality of life for human beings.In this paper, we discuss the design, development and realisation of an innovative technology known as the Georgia Tech Wearable Motherboard (GTWM), or the Smart Shirt. The principal advantage of GTWM is that it provides, for the first time, a very systematic way of monitoring the vital signs of humans in an unobtrusive manner. The flexible databus integrated into the structure transmits the information to monitoring devices such as an EKG machine, a temperature recorder, a voice recorder, etc. GTWM is lightweight and can be worn easily by anyone, from infants to senior citizens. We present the universal characteristics of the interface pioneered by the Georgia Tech Wearable Motherboard and explore the potential applications of the technology in areas ranging from combat to geriatric care. The GTWM is the realisation of a personal information processing system that gives new meaning to the termubiquitous computing. Just as the spreadsheet pioneered the field of information processing that brought computing to the masses, it is anticipated that the Georgia Tech Wearable Motherboard will bring personalised and affordable healthcare monitoring to the population at large.     

Provably good approximation algorithms for optimal kinodynamic planning for Cartesian robots and open-chain manipulators

Inoptimal kinodynamic planning, given a robot system, we must find a minimal-time trajectory that goes from a start state to a goal state while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. With Canny and Reif [1], we approached this problem from an-approximation standpoint and introduced a provably good approximation algorithm for optimal kinodynamic planning for a robot obeying particle dynamics. If a solution exists, this algorithm returns a trajectory-close to optimal in time polynomial in both (1/) and the geometric complexity.We extend [1] and [2] tod-link three-dimensional robots with full rigid-body dynamics amidst obstacles. Specifically, we describe polynomial-time approximation algorithms for Cartesian robots obeyingL ₂ dynamic bounds and for open-kinematic-chain manipulators with revolute and prismatic joints. The latter class includes many industrial manipulators. The correctness and complexity of these algorithms rely on new trajectory tracking lemmas for robots with coupled dynamics bounds.This paper describes research done at the Computer Science Robotics Laboratory at Cornell University. Support for our robotics research there is provided in part by the National Science Foundation under Grant Nos. IRI-8802390 and IRI-9000532, by a Presidential Young Investigator award, and in part by the Mathematical Sciences Institute, Intel Corporation, and AT&T Bell Laboratories.     

Mechanical procedure for proof construction via closed terms in typed λ calculus

In this paper is presented an algorithm for constructing natural deduction proofs in the propositional intuitionistic and classical logics according to the analogy relating intuitionistic propositional formulas and natural deduction proofs, respectively, to types and terms of simple type theory. Proofs are constructed as closed terms in the simple typed calculus. The soundness and completeness of this method are proved.