Bøger i Nato ASI Subseries F: serien

The Marktoberdorf Summer School 1995 'Logic of Computation' was the 16th in a series of Advanced Study Institutes under the sponsorship of the NATO Scientific Affairs Division held in Marktoberdorf. Its scientific goal was to survey recent progress on the impact of logical methods in software development. The courses dealt with many different aspects of this interplay, where major progress has been made. Of particular importance were the following. ¿ The proofs-as-programs paradigm, which makes it possible to extract verified programs directly from proofs. Here a higher order logic or type theoretic setup of the underlying language has developed into a standard. ¿ Extensions of logic programming, e.g. by allowing more general formulas and/or higher order languages. ¿ Proof theoretic methods, which provide tools to deal with questions of feasibility of computations and also to develop a general mathematical understanding of complexity questions. ¿ Rewrite systems and unification, again in a higher order context. Closely related is the now well-established Grabner basis theory, which recently has found interesting applications. ¿ Category theoretic and more generally algebraic methods and techniques to analyze the semantics of programming languages. All these issues were covered by a team of leading researchers. Their courses were grouped under the following headings.

This book is a thoroughly revised result, updated to mid-1995, of the NATO Advanced Research Workshop on "Intelligent Learning Environments: the case of geometry", held in Grenoble, France, November 13-16, 1989. The main aim of the workshop was to foster exchanges among researchers who were concerned with the design of intelligent learning environments for geometry. The problem of student modelling was chosen as a central theme of the workshop, insofar as geometry cannot be reduced to procedural knowledge and because the significance of its complexity makes it of interest for intelligent tutoring system (ITS) development. The workshop centred around the following themes: modelling the knowledge domain, modelling student knowledge, design­ ing "didactic interaction", and learner control. This book contains revised versions of the papers presented at the workshop. All of the chapters that follow have been written by participants at the workshop. Each formed the basis for a scheduled presentation and discussion. Many are suggestive of research directions that will be carried out in the future. There are four main issues running through the papers presented in this book: ¿ knowledge about geometry is not knowledge about the real world, and materialization of geometrical objects implies a reification of geometry which is amplified in the case of its implementation in a computer, since objects can be manipulated directly and relations are the results of actions (Laborde, Schumann). This aspect is well exemplified by research projects focusing on the design of geometric microworlds (Guin, Laborde).

Deductive program design aims at methods that guide and support the development of programs by techniques of deduction. Deduction is a well-known subject of study in logical theories. However, the application of deductive techniques in program design needs methods, heuristics, and understanding of the required forms and formats of the development result that go far beyond those found in logical theories. The summer school presents a very broad spectrum of approaches to these issues. Edsger W. Dijkstra gives a number of beautiful examples that show how to design proofs. Samson Abramsky, Simon Gay, and Rajagopal Nagarajan contribute a fundamental study founding concurrent programming on interaction categories and foundations of type theory. Tony Hoare presents unifying views on mathematical models for computing science. Unifying theories are especially important if the whole development process of programs is to be supported by deductive techniques. The rest of the contributions address applications of deductive program design methods. They are directed to different areas of application; for example Richard Bird's and Oege de Moor's algebra of programming is mainly intended for classical functional programming, and the contribution on data refinement and their transformation by David Gries considers sequential procedural programs.

This volume is an outgrowth of a NATO Advanced Research Workshop on "Expert Judgment and Expert Systems," held in Porto, Portugal, August 1986. Support for the Workshop was provided by the NATO Division of Scientific Affairs, the U.S. Army Research Institute, and the U.S. National Science Foundation. The Workshop brought together researchers from the fields of psychology, decision analysis, and artificial intelligence. The purposes were to assess similarities, differences, and complementarities among the three approaches to the study of expert judgment; to evaluate their relative strengths and weaknesses; and to propose profitable linkages between them. Each of the papers in the present volume is directed toward one or more of those goals. We wish to express our appreciation and thanks to the following persons for their support and assistance: John Adams, Vincent T. Covello, Luis da Cunha, Claire Jeseo, B. Michael Kantrowitz, Margaret Lally, Judith Orasanu, R. M. Rodrigues, and Sandor P. Schuman.

Constraint programming is like an octopus spreading its tentacles into databases, operations research, artificial intelligence, and many other areas. The concept of constraint programming was introduced in artificial intelligence and graphics in the 1960s and 1970s. Now the related techniques are used and studied in many fields of computing. Different aspects of constraint processing are investigated in theoretical computer science, logic programming, knowledge representation, operations research, and related application domains. Constraint programming has been included in the lists of related topics of many conferences. Nevertheless, only in 1993 were the first forums held, devoted as a whole to this field of knowledge. These were the First Workshop on Principles and Practice of Constraint Programming (PPCP'93) which was held in Newport, Rhode Island, USA, April 28-30, the International Workshop on Constraint Processing (at CSAM'93) held in St. Petersburg, Russia, July 20-21, and the NATO Advanced Study Institute (NATO AS!) on Constraint Programming held in Parnu, Estonia, August 13-24. NATO A Sis are aimed to be schools bringing together leading researchers and practitioners from industry and academia in some area of knowledge to provide a concise picture of the work done and results obtained by different groups. This is intended for dissemination of advanced knowledge not yet taught regularly in of new topics university. However, ASis must also encourage the introduction into university curricula as well as foster international scientific contacts.

NATO's Division of Scientific and Environmental Affairs sponsored this Advan­ ced Study Institute because it was felt to be timely to cover this important and challengjng subject for the first time in the framework of NATO's ASI programme. The significance of real-time systems in everyones' life is rapidly growing. The vast spectrum of these systems can be characterised by just a few examples of increasing complexity: controllers in washing machines, air traffic control systems, control and safety systems of nuclear power plants and, finally, future military systems like the Strategic Defense Initiative (SDI). The import­ ance of such systems for the well-being of people requires considerable efforts in research and development of highly reliable real-time systems. Furthermore, the competitiveness and prosperity of entire nations now depend on the early app­ lication and efficient utilisation of computer integrated manufacturing systems (CIM), of which real-time systems are an essential and decisive part. Owing to its key significance in computerised defence systems, real-time computing has also a special importance for the Alliance. The early research and development activities in this field in the 1960s and 1970s aimed towards improving the then unsatisfactory software situation. Thus, the first high-level real-time languages were defined and developed: RTL/2, Coral 66, Procol, LTR, and PEARL. In close connection with these language develop­ ments and with the utilisation of special purpose process control peripherals, the research on real-time operating systems advanced considerably.

Historically, one of the basic issues in control systems design has been robustness: the ability of a controlled plant to withstand variations in or lack of knowledge of its dynamics. Even if the dynamics of a system are accurately known for purposes of implementation, it is often desirable to design a control system based on a simplified model. Consequently it is essential to be able to guarantee a reasonable performance not only for the nominal plant, but also for its neighbouring perturbations: this is the issue of robustness. Since the beginning of this decade major advances have been made in this area, notably using the H -approach; this term is meant to cover the solution of sensitivity reduction, approximation and model reduction, robustness and related control design problems using the mathematics of Hardy spaces and related areas in Harmonic Analysis. This book contains the proceedings of the NATO Advanced Research Workshop on "Modelling, Robustness and Sensitivity Reduction in Control Systems", which was held at the University of Groningen, December 1986. Its aim was to explore the development of H -design techniques and its ramifications in Systems Theory in a unified and systematic way with the emphasis on recent advances and future directions in this fast developing area. In particular the following inter-related aspects were addressed: H -mathematical foundations, model approximation and robustness in control design, optimal sensitivity reduction, modelling and system identification and signal processing.

These proceedings contain lectures presented at the NATO-NSF-ARO sponsored Advanced Study I~stitute on "Computer Aided Analysis and Optimization of Mechanical System Dynamics" held in Iowa City, Iowa, 1-12 August, 1983. Lectures were presented by free world leaders in the field of machine dynamics and optimization. Participants in the Institute were specialists from throughout NATO, many of whom presented contributed papers during the Institute and all of whom participated actively in discussions on technical aspects of the subject. The proceedings are organized into five parts, each addressing a technical aspect of the field of computational methods in dynamic analysis and design of mechanical systems. The introductory paper presented first in the text outlines some of the numerous technical considerations that must be given to organizing effective and efficient computational methods and computer codes to serve engineers in dynamic analysis and design of mechanical systems. Two substantially different approaches to the field are identified in this introduction and are given attention throughout the text. The first and most classical approach uses a minimal set of Lagrangian generalized coordinates to formulate equations of motion with a small number of constraints. The second method uses a maximal set of cartesian coordinates and leads to a large number of differential and algebraic constraint equations of rather simple form. These fundamentally different approaches and associated methods of symbolic computation, numerical integration, and use of computer graphics are addressed throughout the proceedings.

As robots improve in efficiency and intelligence, there is a growing need to develop more efficient, accurate and powerful sensors in accordance with the tasks to be robotized. This has led to a great increase in the study and development of different kinds of sensor devices and perception systems over the last ten years. Applications that differ from the industrial ones are often more demanding in sensorics since the environment is not usually so well structured. Spatial and agricultural applications are examples of situations where the environment is unknown or variable. Therefore, the work to be done by a robot cannot be strictly programmed and there must be an interactive communication with the environment. It cannot be denied that evolution and development in robotics are closely related to the advances made in sensorics. The first vision and force sensors utilizing discrete components resulted in a very low resolution and poor accuracy. However, progress in VLSI, imaging devices and other technologies have led to the development of more efficient sensor and perception systems which are able to supply the necessary data to robots.