For some years, specification of software and hardware systems has been influenced not only by algebraic methods but also by new developments in logic. These new developments in logic are partly based on the use of algorithmic techniques in deduction and proving methods, but are alsodue to new theoretical advances, to a great extent stimulated by computer science, which have led to new types of logic and new logical calculi. The new techniques, methods and tools from logic, combined with algebra-based ones, offer very powerful and useful tools for the computer scientist, which may soon become practical for commercial use, where, in particular, more powerful specification tools are needed for concurrent and distributed systems. This volume contains papers based on lectures by leading researchers which were originally given at an international summer school held in Marktoberdorf in 1991. The papers aim to give a foundation for combining logic and algebra for the purposes of specification under the aspects of automated deduction, proving techniques, concurrency and logic, abstract data types and operational semantics, and constructive methods.

This third volume documents the results achieved within a priority program on spatial cognition funded by the German Science Foundation (DFG). The 23 revised full papers presented went through two rounds of reviewing and improvement and reflect the increased interdisciplinary cooperation in the area. The papers are organized in topical sections on routes and navigation, human memory and learning, spatial representation, and spatial reasoning.

This book presents state of the art research in theoretical computer science and related ?elds. In particular, the following areas are discussed: automata theory, formal languages and combinatorics of words, graph transformations, Petri nets, concurrency, as well as natural and molecular computing. The articles are written by leading researchers in these areas. The writers were originally invited to contribute to this book but then the normal refereeing procedure was applied as well. All of the articles deal with some issue that has been under vigorous study during recent years. Still, the topics range from very classical ones to issues raised only two or three years ago. Both survey articles and papers attacking speci?c research problems are included. The book highlights some key issues of theoretical computer science, as they seem to us now at the beginning of the new millennium. Being a comprehensive overview of some of the most active current research in theoretical computer science, it should be of de?nite interest for all researchers in the areas covered. The topics range from basic decidability and the notion of information to graph grammars and graph transformations, and from trees and traces to aqueous algorithms, DNA encoding and self-assembly. Special e?ort has been given to lucid presentation. Therefore, the book should be of interest also for advanced students.

Spatialcognitionisconcernedwiththewayshumans,animals,ormachinesthink about real or abstract space and also with the ways spatial structures can be used for reasoning. Thus, space is considered both, as an object of cognition and as ameans of cognition. Spatial cognition is an interdisciplinary research areainvolvingapproachesfromarti?cialintelligence,cognitivepsychology,ge- raphy, mathematics, biology, design, theoretical computer science, architecture, andphilosophy.Researchonspatialcognitionhasprogressedrapidlyduringthe past few years. The disciplines contributing to the ?eld have moved closer - getherandbegintospeakacommonlanguage.Theyhavefoundwaysofmerging theresearchresultsobtainedthroughdi?erentapproaches.Thisallowsfordev- oping more sophisticated hybrid approaches that overcome intrinsic limitations of the individual disciplines. Research on spatial cognition has drawn increased attention in recent years foratleastthreedi?erentreasons:(1)basicresearchdimension:thereisagr- ing awareness of the importance of spatial cognitive abilities in biological s- tems, speci?cally with respect to perception and action, to the organization of memory, and to understanding and producing natural language; (2) compu- tionaldimension:spatialrepresentationsandspatialinferencemayprovidesu- ablelimitationsto enhancethe computationale? ciencyforalargeandrelevant class of problems; (3) application dimension: a good understanding of spatial processes is essential for a wide variety of challenging application areas incl- ing Geographic Information Systems (GIS), pedestrian and vehicle navigation aids,autonomousrobots,smartgraphics,medicalsurgery,informationretrieval, virtual reality, Internet navigation, and human-computer interfaces. This is the second volume published in the framework of the Spatial Cog- tion Priority Program. It augments the results presented in Freksa et al. 1998.

This book constitutes the proceedings of the 19th Annual German Conference on Artificial Intelligence, KI-95, held in Bielefeld in September 1995.
The volume opens with full versions of four invited papers devoted to the topic "From Intelligence Models to Intelligent Systems." The main part of the book consists of 17 refereed full papers carefully relected by the program committee; these papers are organized in sections on knowledge organization and optimization, logic and reasoning, nonmonotonicity, action and change, and spatial reasoning.

For some years, specification of software and hardware systems has been influenced not only by algebraic methods but also by new developments in logic. These new developments in logic are partly based on the use of algorithmic techniques in deduction and proving methods, but are alsodue to new theoretical advances, to a great extent stimulated by computer science, which have led to new types of logic and new logical calculi. The new techniques, methods and tools from logic, combined with algebra-based ones, offer very powerful and useful tools for the computer scientist, which may soon become practical for commercial use, where, in particular, more powerful specification tools are needed for concurrent and distributed systems. This volume contains papers based on lectures by leading researchers which were originally given at an international summer school held in Marktoberdorf in 1991. The papers aim to give a foundation for combining logic and algebra for the purposes of specification under the aspects of automated deduction, proving techniques, concurrency and logic, abstract data types and operational semantics, and constructive methods.

Petri Nets represent a long and sustained effort. to develop concepts, theories and tools to aid in design and analysis of concurrent systems. They are used in many areas of computer science including software engineering, data base and in formation systems, computer architecture and operating systems, communication protocols and computer networks, process control, and socio-technical systems such as office communication and man-machine interaction. Quite substantial theory has been developed for Petri Nets. It reflects all major problem areas of concurrent distributed systems and covers many successfully applied principles and analysis techniques for systems organisation. Since the time that C. A. Petri has presented his original ideas, a rich body of knowledge has been developed-a recent bibliography (in Advances in Petri Nets 1981) includes more than 2000 entries. Already in 1979 an Advanced Course on Petri Nets was organized in Hamburg, West Germany, aiming at systematizing the existing knowledge and making it well accessible to a wide audience of computer scientists interested in theory and applications of concurrent systems. This course has turned out to be successful in the sense that it has initiated a lot of new research into applications and theory of Petri Nets. This had led to. another Advanced Course in 1986 in Bad Honnef, West Germany - where during two weeks more than 30 lectures were presented covering the most important current developments in the area of Petri Nets."

The present volume is the second of two parts which constitute the proceedings of the 1986 Advanced Course on Petri Nets in Bad Honnef. It discusses tools supporting the design of petri nets as well as their modification and analysis, presents a variety of applications, and covers the relationship of petri nets to other concurrency models. These current issues of the "Advances in Petri Nets" present the most significant recent results in the application and theory of petri nets to the broad computer science community. They particularly address those who are: - interested in systems design and would like to learn to use petri nets, - familiar with subareas of the theory or the applications of nets and wish to become acquainted with the whole area, - interested in learning about recent results presented within a unified framework, - going to learn about successfully applying petri nets in - various practical situations, - interested in the relationship of petri nets to other models of concurrent systems.

Durch die Reihe der GI-Kongresse uber wissensbasierte Systeme wird eine groessere OEffentlichkeit uber den Stand der Entwicklung sowohl in den Entwurfsmethoden und Konstruktionstechniken als auch in der industriellen Anwendung unterrichtet. Ein wichtiges Ziel ist dabei, auf das grosse Potential an Anwendungsmoeglichkeiten hinzuweisen und intensivere Kooperation zwischen verschiedenen Gebieten anzuregen. Behandelt werden diesmal neben den Grundlagen, Entwicklungen und Anwendungen von Expertensystemen auch maschinelles Lernen, naturlichsprachliche Systeme und Konnektionismus. Einen grossen Raum nimmt die Prasentation von Gemeinschaftsprojekten ein; insbesondere werden deutsche KI-Zentren, alle BMFT-Verbundprojekte im Bereich wissensbasierter Systeme und zahlreiche europaische Gemeinschaftsprojekte (EUREKA- und ESPRIT-Projekte) dargestellt. Dieses Buch wendet sich an alle, die Interesse an der Informatik und ihren Anwendungen haben. Es soll sowohl Wissenschaftler als auch Praktiker und moegliche Anwender informieren und zu fruchtbarer Diskussion und Zusammenarbeit stimulieren.

Dieses Buch enthalt die Beitrage einer Tagung, die gemeinsam vom Fachbereich "Ausbildung und Beruf" der Gesellschaft fur Informatik und dem Institut fur Film und Bild in Wissenschaft und Unterricht FWU veranstaltet wurde. Die absehbare technische Weiterentwicklung des Computers in der Hardware und der Software offnet der Ausbildung viele Wege in die Zukunft. Dies belegt eindrucksvoll der Themenkatalog der Tagung: Ausbildung an allgemeinen und berufsbildenden Schulen, betriebliche Ausbildung, Netze und Telekommunikation, Computer-unterstutztes Lernen und Anwenden im Schulunterricht.

Wissensbasierte Systeme wurden in den letzten Jahren uber die Stadien des Experimentierens, der Forschung und der Entwicklung hinaus zu interessanten Produkten der Informationsindustrie und werden immer mehr zu wichtigen Arbeitsmitteln fur Fachleute und Mitarbeiter in der Wirtschaft, in der Verwaltung und im Bildungsbereich. Die GI-Kongresse uber wissensbasierte Systeme sollen eine grossere Offentlichkeit uber den Stand der Entwicklung unterrichten, sowohl in den Entwurfsmethoden und Konstruktionstechniken als auch in der industriellen Anwendung. Ein wesentliches Ziel dabei ist es, auf das grosse Potential an Anwendungsmoglichkeiten hinzuweisen und intensivere Kooperationen zwischen verschiedenen Gebieten anzuregen. Im vorliegenden Tagungsband des 2. Internationalen GI-Kongresses "Wissensbasierte Systeme", der 1987 wieder im Rahmen der Fachmesse SYSTEMS in Munchen stattfand, werden neben den Expertensystemen im engeren Sinne auch graphische Systeme, Techniken der Computeranimation, kooperative Hilfssysteme, intelligente tutorielle Systeme und entscheidungsunterstutzende Systeme behandelt. Grossen Raum nimmt die Prasentation von Gemeinschaftsprojekten ein; insbesondere werden die KI-Verbundprojekte des BMFT und eine Reihe von ESPRIT-Projekten vorgestellt. Dieses Buch wendet sich an alle, die Interesse an Informatik und ihren Anwendungen haben; es soll nicht nur Wissenschaftler, sondern insbesondere auch Praktiker und mogliche Anwender informieren und zu neuen Ideen anregen. Und es soll Wissenschaft und Praxis zu fruchtbarer Diskussion und Zusammenarbeit stimulieren. Neben vielen deutschen Autoren aus Forschung und Praxis kommen Wissenschaftler aus mehreren europaischen Landern und aus den USA zu Wort.

Entwicklungen gerecht zu werden versucht - auf eine Diskussion der verschiedenen und zum Teil recht uneinheitlichen Bezeich nungsweisen, die in der Literatur verwendet werden, wurde ver zichtet; gelegentlich werden jedoch einige Anmerkungen im je weiligen Abschnitt uber Literaturhinweise und historische Be merkungen gemacht. Diese Abschnitte sind jedoch vor allem dazu da, die Erstveroffentlichungen der dargestellten Ideen und Re sultate anzugeben, ferner werden dort auch einige erganzende Arbeiten und viele Lehrbucher zitiert. Im Text wird nicht spe ziell auf die Literatur verwiesen. Die zahlreichen Aufgaben dienen zur tJbung und Vertiefung aber auch zur Erganzung des Stoffes (besonders schwierige Aufgaben sind mit einem * gekennzeichnet). Sie sind ein wichtiger Be standteil des Buches und sollten, wenn schon nicht samtlich ausfuhrlich gelost, so doch wenigstens aufmerksam gelesen und uberdacht werden. Um die Orientierung zu erleichtern, wurde das Inhaltsverzeich nis mit kurzen Inhaltsangaben der einzelnen Abschnitte ver sehen, und es wurden diejenigen Abschnitte durch Unterstrei chung ihrer Nummern hervorgehoben, die die zentralen Teile der Automatentheorie enthalten, die zum Grundwissen eines jeden Informatikers gehoren sollten und schon im Grundstudium gelehrt werden konnen."