Current Trends In Theoretical Computer Science Entering The 21st Century

This book is based on columns and tutorials published in the Bulletin of the European Association for Theoretical Computer Science (EATCS) during the period 2000OCo2003. It presents many of the most active current research lines in theoretical computer science. The material appears in two volumes, OC Algorithms and ComplexityOCO and OC Formal Models and SemanticsOCO, reflecting the traditional division of the field. The list of contributors includes many of the well-known researchers in theoretical computer science. Most of the articles are reader-friendly and do not presuppose much knowledge of the area in question. Therefore, the book constitutes very suitable supplementary reading material for various courses and seminars in computer science. Contents: Vol 1: Algorithms; Computational Complexity; Distributed Computing; Natural Computing; Vol 2: Formal Specification; Logic in Computer Science; Concurrency; Formal Language Theory. Readership: Upper level undergraduates, graduate students and researchers in theoretical computer science and biocomputing."

The scientific developments at the end of the past millennium were dominated by the huge increase and diversity of disciplines with the common label OC computer scienceOCO. The theoretical foundations of such disciplines have become known as theoretical computer science . This book highlights some key issues of theoretical computer science as they seem to us now, at the beginning of the new millennium. The text is based on columns and tutorials published in the Bulletin of the European Association for Theoretical Computer Science in the period 1995OCo2000. The columnists themselves selected the material they wanted for the book, and the editors had a chance to update their work. Indeed, much of the material presented here appears in a form quite different from the original. Since the presentation of most of the articles is reader-friendly and does not presuppose much knowledge of the area, the book constitutes suitable supplementary reading material for various courses in computer science. Contents: Computational Complexity (E Allender et al.); Formal Specification (H Ehrig et al.); Login in Computer Science (Y Gurevich et al.); Concurrency (M Nielsen et al.); Natural Computing (G Rozenberg et al.); Formal Language Theory (A Salomaa et al.). Readership: Researchers, graduate students and senior undergraduates in computer science."

contents: vol 1 : Algorithms; Computational Complexity; Distributed Computing; Natural Computing.

By presenting state-of-the-art research results on various aspects of formal and visual modeling of software and systems, this book commemorates the 60th birthday of Hartmut Ehrig. The 24 invited reviewed papers are written by students and collaborators of Hartmut Ehrig who are established researchers in their fields. Reflecting the scientific interest and work of Hartmut Ehrig, the papers fall into three main parts on graph transformation, algebraic specification and logic, and formal and visual modeling.

This book constitutes the refereed proceedings of the 27th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007, held in New Delhi, India, in December 2007. The 40 revised full papers presented together with 5 invited papers were carefully reviewed and selected from 135 submissions. The papers provide original research results in fundamental aspects of computer science as well as reports from the frontline of software technology and theoretical computer science. A broad variety of current topics from the theory of computing are addressed, ranging from software science, programming theory, systems design and analysis, formal methods, mathematical logic, mathematical foundations, discrete mathematics, combinatorial mathematics, complexity theory, and automata theory to theoretical computer science in general.

. . . . . . . . . . . . . . . . 328 D. Sannella AuthorIndex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 InteractiveRule-BasedSpeci?cationwithan ApplicationtoVisualLanguageDe?nition 1 1 2 Roswitha Bardohl , Martin Große-Rhode , and Marta Simeoni 1 Institutfur ̈ SoftwaretechnikundTheoretischeInformatik,TUBerlin, {rosi,mgr}@cs. tu-berlin. de 2 DipartimentodiInformatica,Universit`aCa`FoscaridiVenezia, simeoni@dsi. unive. it Abstract. Inarule-basedapproachthecomputationstepsofasystem arespeci?edbyrulesthatcompletelyde?nehowthesystem’sstatemay change. Foropensystemsamoreliberalapproachisrequired,wherethe statechangesareonlypartlyspeci?ed,and–interactively–otherc- ponents may contribute further information on how the transformation isde?nedcompletely.

Communicating Process Architecture (CPA) describes an approach to system development that is process-oriented. It makes no great distinction between hardware and software. It has a major root in the theory of Communicating Sequential Processes (CSP). However, the underlying theory is not limited to CSP. The importance of mobility of both channel and process within a network sees integration with ideas from the ð-calculus. Other formalisms are also exploited, such as BSP and MPI. The focus is on sound methods for the engineering of significant concurrent systems, including those that are distributed (across the Internet or within a single chip) and/or software-scheduled on a single execution unit. Traditionally, at CPA, the emphasis has been on theory and practice - developing and applying tools based upon CSP and related theories to build high-integrity systems of significant size. In particular, interest focuses on achieving scalability and security against error. The development of Java, C, and C++, libraries to facilitate secure concurrent programming using 'mainstream' languages has allowed CPA to continue and proliferate. This work continues in support of the engineering of distributed applications. Recently, there has been greater reference to theory and its more direct application to programming systems and languages. In this volume the formal CSP is very well presented. The papers provide a healthy mixture of the academic and commercial, software and hardware, application and infrastructure, which reflects the nature of the discipline.