This book constitutes the proceedings of the 15th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2012, held as part of the joint European Conference on Theory and Practice of Software, ETAPS 2012, which took place in Tallinn, Estonia, in March/April 2012. The 29 papers presented in this book together with two invited talks in full paper length were carefully reviewed and selected from 100 full paper submissions. The papers deal with theories and methods to support analysis, synthesis, transformation and verification of programs and software systems.

This book constitutes the refereed proceedings of the 15th International Conference on Fundamental Approaches to Software Engineering, FASE 2012, held in Tallinn, Estonia, in March/April 2012, as part of ETAPS 2012, the European Joint Conferences on Theory and Practice of Software. The 33 full papers presented together with one full length invited talk were carefully reviewed and slected from 134 submissions. The papers are organized in topical sections on software architecture and components, services, verification and monitoring, intermodelling and model transformations, modelling and adaptation, product lines and feature-oriented programming, development process, verification and synthesis, testing and maintenance, and slicing and refactoring.

Welcome to the 5th International Conference on Open Source Systems! It is quite an achievement to reach the five-year mark - that's the sign of a successful enterprise. This annual conference is now being recognized as the primary event for the open source research community, attracting not only high-quality papers, but also building a community around a technical program, a collection of workshops, and (starting this year) a Doctoral Consortium. Reaching this milestone reflects the efforts of many people, including the conference founders, as well as the organizers and participants in the previous conferences. My task has been easy, and has been greatly aided by the hard work of Kevin Crowston and Cornelia Boldyreff, the Program Committee, as well as the Organizing Team led by Bjoern Lundell. All of us are also grateful to our attendees, especially in the difficult economic climate of 2009. We hope the participants found the conference valuable both for its technical content and for its personal networking opportunities. To me, it is interesting to look back over the past five years, not just at this conference, but at the development and acceptance of open source software. Since 2004, the business and commercial side of open source has grown enormously. At that time, there were only a handful of open source businesses, led by RedHat and its Linux distribution. Companies such as MySQL and JBoss were still quite small.

This book constitutes the refereed proceedings of the 21st European Symposium on Programming, ESOP 2012, held in Tallinn, Estonia, as part of ETAPS 2012, in March/April 2012. The 28 full papers, presented together with one full length invited talk, were carefully reviewed and selected from 92 submissions. Papers were invited on all aspects of programming language research, including: programming paradigms and styles, methods and tools to write and specify programs and languages, methods and tools for reasoning about programs, methods and tools for implementation, and concurrency and distribution.

2 Source Code Availability All of the source code in this volume, and some that is not, is available from the author for $20. The author is also interested in learning of any errors that may be found, though care has been taken in the construction of the modules to minimize the possibility of their occurence. Any other comments, suggestions, recommenda- tions, questions, or experiences with the use of these modules would also be of interest. The reader may contact the author via the publisher at the following address: C. Lins: Modula-2 Source Code c/o Springer-Verlag 815 De La Vina Street Santa Barbara, CA 93101 USA As of February 1989, source code is available on two 3. 5" Macintosh diskettes (800K HFS format) for Bob Campbell's Modula-2 compiler for MPW(formerly TML Modula-2) and the MacMETH Modula-2 compiler from ETH Zurich. The author intends to port this software to both the SemperSoft and MetCom Modula- 2 compilers on the Macintosh. For the IBM PC (and compatibles) the software is available for TopSpeed Modula-2 (a product of JPI). The source code will soon be converted to work with Logitech's Modula-2 compiler as well as Stony Brook's Modula-2. Please mention your hardware platform as well as the volume(s) in which you are interested Development Environment The software for this volume was developed using the MPW (Macintosh(TM) Programmer' s Workshop) version 3. 0 and Bob Campbell's Modula-2 compiler ver- sion 1. 4d7.

This book is the first volume in a series entitled The Modula-2 Software Component Library. Charles Lins collection of reusable standard software components, could be the basis for every programmers software project in Modula-2. Components that are implementations of commonly used data structures are presented, along with an adequate description of their functionality and efficiency. Moreover, the books provide the background necessary to tailor these components to the specific needs of any Modula-2 environment. For every Modula-2 programmer this series of books might prove as useful and indispensible as the original language reference by Niklaus Wirth.

The programming language SETL is a relatively new member of the so-called "very-high-level" class of languages, some of whose other well-known mem bers are LISP, APL, SNOBOL, and PROLOG. These languages all aim to reduce the cost of programming, recognized today as a main obstacle to future progress in the computer field, by allowing direct manipulation of large composite objects, considerably more complex than the integers, strings, etc., available in such well-known mainstream languages as PASCAL, PL/I, ALGOL, and Ada. For this purpose, LISP introduces structured lists as data objects, APL introduces vectors and matrices, and SETL introduces the objects characteristic for it, namely general finite sets and maps. The direct availability of these abstract, composite objects, and of powerful mathematical operations upon them, improves programmer speed and pro ductivity significantly, and also enhances program clarity and readability. The classroom consequence is that students, freed of some of the burden of petty programming detail, can advance their knowledge of significant algorithms and of broader strategic issues in program development more rapidly than with more conventional programming languages."

One must be able to say at all times - in stead of points, straight lines, and planes - tables, chairs and beer mugs. (David Hilbert) One service mathematics has rendered the human race. It has put common sense back where it belongs, on the topmost shelf next to the dusty canister labelled "discarded nonsense. " (Eric T. Bell) This book discusses reasoning with partial information. We investigate the proof theory, the model theory and some applications of reasoning with par tial information. We have as a goal a general theory for combining, in a principled way, logic formulae expressing partial information, and a logical tool for choosing among them for application and implementation purposes. We also would like to have a model theory for reasoning with partial infor mation that is a simple generalization of the usual Tarskian semantics for classical logic. We show the need to go beyond the view of logic as a geometry of static truths, and to see logic, both at the proof-theoretic and at the model-theoretic level, as a dynamics of processes. We see the dynamics of logic processes bear with classical logic, the same relation as the one existing between classical mechanics and Euclidean geometry."

Topics * what this book is about, * its intended audience, * what the reader ought to know, * how the book is organized, * acknowledgements. Specifications express information about a program that is not normally part of the program, and often cannot be expressed in a programming lan guage. In the past, the word "specification" has sometimes been used to refer to somewhat vague documentation written in English. But today it indicates a precise statement, written in a machine processable language, about the purpose and behavior of a program. Specifications are written in languages that are just as precise as programming languages, but have additional capabilities that increase their power of expression. The termi nology formal specification is sometimes used to emphasize the modern meaning. For us, all specifications are formal. The use of specifications as an integral part of a program opens up a whole new area of programming - progmmming with specifications. This book describes how to use specifications in the process of building programs, debugging them, and interfacing them with other programs. It deals with a new trend in programming - the evolution of specification languages from the current generation of programming languages. And it describes new strategies and styles of programming that utilize specifications. The trend is just beginning, and the reader, having finished this book, will viii Preface certainly see that there is much yet to be done and to be discovered about programming with specifications.

Prolog has a declarative style. A predicate definition includes both the input and output parameters, and it allows a programmer to define a desired result without being concerned about the detailed instructions of how it is to be computed. Such a declarative language offers a solution to the software crisis, because it is shorter and more concise, more powerful and understandable than present-day languages. Logic highlights novel aspects of programming, namely using the same program to compute a relation and its inverse, and supporting deductive retrieval of informa tion. This is a book about using Prolog. Its real point is the examples introduced from Chapter 3 onwards, and so a Prolog programmer does not need to read Chapters 1 and 2, which are oriented more to teachers and to students, respec tively. The book is recommended for introductory and advanced university courses, where students may need to remember the basics about logic program ming and Prolog, before starting doing. Chapters 1 and 2 were also kept for the sake of unity of the whole material. In Chapter 1 a teaching strategy is explained based on the key concepts of Pro log which are novel aspects of programming. Prolog is enhanced as a computer programming language used for solving problems that involve objects and the relationships between objects. This chapter provides a pedagogical tour of pre scriptions for the organization of Prolog programs, by pointing out the main draw backs novices may encounter."

Augmented Transition Network Grammars are at present the most widely used method for analyzing natural languages. Despite the increasing po pularity of this method, however, no extensive papers on ATN-Grammars have been presented which would be accessible to a larger number of per sons engaged in the problem from both the theoretical and practical points of view. Augmented Transition Networks (ATN) are derived from state automata. Like a finite state automaton, an ATN consists of a collection of la beled states and arcs, a distinguished start state and a set of distin guished final states. States are connected with each other by arcs crea ting a directed graph or net. The label on an arc indicates a terminal symbol (word) or the type of words which must occur in an input stream to allow the transition to the next state. It is said that a sequence of words (or sentence) is accepted by such a net if there exists a se quence of arcs (usually called a path), connecting the start state with a final state, which can be followed to the sentence. The finite state automaton is then enriched by several facilities which increase its computational power. The most important of them permits some arcs to be labeled by nonterminal rather than terminal symbols. This means that the transition through such an arc is actually the re cursive application of the net beginning with a pointed state."

This book introduces the tools you'll need to program with the packetC language packetC speedsthe development ofapplications that live within computer networks, the kind of programs that provide network functionality for connecting "clients" and "servers and clouds."The simplest examples provide packet switching and routing while more complex examples implement cyber security, broadband policies or cloud-based network infrastructure. Network applications, such as those processing digital voice and video, must be highly scalable, secure and maintainable. Such application requirements translate to requirements for a network programming language that leverages massively-parallel systems and ensures a high level of security, while representing networking protocols and transactions in the simplest way possible. packetC meets these requirements with an intuitive approach to coarse-grained parallelism, with strong-typing and controlled memory access for security and with new data types and operators that express the classic operations of the network-oriented world in familiar programming terms. No other language has addressed the full breadth of requirements for tractable parallelism, secure processing and usable constructs. The packetC language is growing in adoption and has been used to develop solutions operating in some of the world's largest networks. What you'll learn This book is the primary document specifying the language from a developer's point of view and act as the formal language user's guide. It covers: How to program applications in packetC. The parallel programming model of packetC Deviations from C99 and the unique aspects of packetC How to leverage existing C code and the applicability of the C standard libraries Who this book is for

packetC Programming is written for a widevariety of potential programmers. Most importantly, it's for people who need to use packetC to program for the Internet backbone. Still, knowledge of the packetC language will help a much wider array of programmers who need to write effective code that will be optimized for the cloud and workeffectively and efficiently through complex network structures. Finally, readers will learn about how and why packetC is needed, and to better understand the technologies, standards and issues surrounding the 'net. If you really want to understand this level of programming, this book isa must-have Table of Contents PART 1: packetC Background Chapter 1: Origins of packetC Chapter 2: Introduction to packetC Language Chapter 3: Style Guidelines for packetC Programs Chapter 4: Construction of a packetC Program PART 2: Language Reference Chapter 5: VariablesIdentifiers, Basic Scalar Data Types, and Literals Chapter 6: Data Initialization and Mathematical Expressions Chapter 7: Functions Chapter 8: packetC Data Type Fundamentals Chapter 9: C-Style Data Types Chapter 10: Basic Packet Interaction and Operations Chapter 11: Selection Statements Chapter 12: Loops and Flow Control Chapter 13: Exception Handling Chapter 14: Databases Types and Operations Chapter 15: Search Set Types and Operations Chapter 16: Reference Type and Operations Chapter 17: Lock and Unlock Operators Chapter 18: Packet Information Block and System Packet Operations Chapter 19: Descriptor Type and Operations PART 3: Developing Applications Chapter 20: Control Plane and System Interaction Chapter 21: packetC Pre-Processor Chapter 22: Pragmas and Other Key Compiler Directives Chapter 23: Developing Large Applications in packetC Chapter 24: Construction of a packetC Executable Chapter 25: packetC Standard Networking Descriptors Chapter 26: Developing For Performance Chapter 27: Standard Libraries PART 4: Industry Reprints Appendix A: Reference Tables Appendix B: Open Systems Vendors for packetC Appendix C: Glossary Appendix D: CloudShield Products Supporting packetC

"I prefer to view formal methods as tools. the use of which might be helpful." E. W. Dijkstra Algebraic specifications are about to be accepted by industry. Many projects in which algebraic specifications have been used as a design tool have been carried out. What prevents algebraic specifications from breaking through is the absence of introductory descriptions and tools supporting the construction of algebraic specifications. On the one hand. interest from industry will stimulate people to make introductions and tools. whereas on the other hand the existence of introductions and tools will stimulate industry to use algebraic specifications. This book should be seen as a contribution towards creating this virtuous circle. The book will be of interest to software designers and programmers. It can also be used as material for an introductory course on algebraic specifications and software engineering at undergraduate or graduate level. Nowadays. there is general agreement that in large software projects appropriate specifications are a must in order to obtain quality software. Informal specifications alone are certainly not appropriate because they are incomplete. inconsistent. inaccurate and ambiguous and they rapidly become bulky and therefore useless. The only way to overcome this problem is to use formal specifications. An important remark here is that a specification formalism (language) alone is not sufficient. What is also needed is a design method to write specifications in that formalism.

Logical concepts and methods are of growing importance in many areas of computer science. The proofs-as-programs paradigm and the wide acceptance of Prolog show this clearly. The logical notion of a formal proof in various constructive systems can be viewed as a very explicit way to describe a computation procedure. Also conversely, the development of logical systems has been influenced by accumulating knowledge on rewriting and unification techniques. This volume contains a series of lectures by leading researchers giving a presentation of new ideas on the impact of the concept of a formal proof on computation theory. The subjects covered are: specification and abstract data types, proving techniques, constructive methods, linear logic, and concurrency and logic.

This book is a detailed account of the Synthesizer Generator, a system for creat ing specialized editors that are customized for editing particular languages. The book is intended for those with an interest in software tools and in methods for building interactive systems. It is a must for people who are using the Syn thesizer Generator to build editors because it provides extensive discussions of how to write editor specifications. The book should also be valuable for people who are building specialized editors "by hand," without using an editor generating tool. The need to manage the development of large software systems is one of the most pressing problems faced by computer programmers. An important aspect of this problem is the design of new tools to aid interactive program develop ment. The Synthesizer Generator permits one to create specialized editors that are tailored for editing a particular language. In program editors built with the Synthesizer Generator, knowledge about the language is used to continuously assess whether a program contains errors and to determine where such errors occur. The information is then displayed on the terminal screen to provide feed back to the programmer as the program is developed and modified."

The topic of logic programming and databases. has gained in creasing interest in recent years. Several events have marked the rapid evolution of this field: the selection, by the Japanese Fifth Generation Project, of Prolog and of the relational data model as the basis for the development of new machine archi tectures; the focusing of research in database theory on logic queries and on recursive query processing; and the pragmatic, application-oriented development of expert database systems and of knowledge-base systems. As a result, an enormous amount of work has been produced in the recent literature, coupled with the spontaneous growth of several advanced projects in this area. The goal of this book is to present a systematic overview of a rapidly evolving discipline, which is presently not described with the same approach in other books. We intend to introduce stu dents and researchers to this new discipline; thus we use a plain, tutorial style, and complement the description of algorithms with examples and exercises. We attempt to achieve a balance be tween theoretical foundations and technological issues; thus we present a careful introduction to the new language Datalog, but we also focus on the efficient interfacing of logic programming formalisms (such as Prolog and Datalog) with large databases.

In the two and a half years since the frrst edition of this book was published, the field of logic programming has grown rapidly. Consequently, it seemed advisable to try to expand the subject matter covered in the first edition. The new material in the second edition has a strong database flavour, which reflects my own research interests over the last three years. However, despite the fact that the second edition has about 70% more material than the first edition, many worthwhile topic!! are still missing. I can only plead that the field is now too big to expect one author to cover everything. In the second edition, I discuss a larger class of programs than that discussed in the first edition. Related to this, I have also taken the opportunity to try to improve some of the earlier terminology. Firstly, I introduce "program statements", which are formulas of the form A+-W, where the head A is an atom and the body W is an arbitrary formula. A "program" is a finite set of program statements. There are various restrictions of this class. "Normal" programs are ones where the body of each program statement is a conjunction of literals. (The terminology "general", used in the first edition, is obviously now inappropriate).

This book is an anthology of the results of research and development in database query processing during the past decade. The relational model of data provided tremendous impetus for research into query processing. Since a relational query does not specify access paths to the stored data, the database management system (DBMS) must provide an intelligent query-processing subsystem which will evaluate a number of potentially efficient strategies for processing the query and select the one that optimizes a given performance measure. The degree of sophistication of this subsystem, often called the optimizer, critically affects the performance of the DBMS. Research into query processing thus started has taken off in several directions during the past decade. The emergence of research into distributed databases has enormously complicated the tasks of the optimizer. In a distributed environment, the database may be partitioned into horizontal or vertical fragments of relations. Replicas of the fragments may be stored in different sites of a network and even migrate to other sites. The measure of performance of a query in a distributed system must include the communication cost between sites. To minimize communication costs for-queries involving multiple relations across multiple sites, optimizers may also have to consider semi-join techniques.

This book provides a superb introduction to and overview of the MIT PI System for custom VLSI placement and routing. Alan Sher man has done an excellent job of collecting and clearly presenting material that was previously available only in various theses, confer ence papers, and memoranda. He has provided here a balanced and comprehensive presentation of the key ideas and techniques used in PI, discussing part of his own Ph. D. work (primarily on the place ment problem) in the context of the overall design of PI and the contributions of the many other PI team members. I began the PI Project in 1981 after learning first-hand how dif ficult it is to manually place modules and route interconnections in a custom VLSI chip. In 1980 Adi Shamir, Leonard Adleman, and I designed a custom VLSI chip for performing RSA encryp tion/decryption [226]. I became fascinated with the combinatorial and algorithmic questions arising in placement and routing, and be gan active research in these areas. The PI Project was started in the belief that many of the most interesting research issues would arise during an actual implementation effort, and secondarily in the hope that a practically useful tool might result. The belief was well-founded, but I had underestimated the difficulty of building a large easily-used software tool for a complex domain; the PI soft ware should be considered as a prototype implementation validating the design choices made.

This book constitutes the thoroughly refereed post-conference proceedings of the Joint Workshop on Theory of Security and Applications (formely known as ARSPA-WITS), TOSCA 2011, held in Saarbrucken, Germany, in March/April 2011, in association with ETAPS 2011. The 9 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 24 submissions. The papers feature topics including various methods in computer security, including the formal specification, analysis and design of security protocols and their applications, the formal definition of various aspects of security such as access control mechanisms, mobile code security and denial-of-service attacks, and the modeling of information flow and its application.

This book comprises selected papers of the International Conferences, ASEA, DRBC and EL 2011, held as Part of the Future Generation Information Technology Conference, FGIT 2011, in Conjunction with GDC 2011, Jeju Island, Korea, in December 2011. The papers presented were carefully reviewed and selected from numerous submissions and focuse on the various aspects of advances in software engineering and its Application, disaster recovery and business continuity, education and learning.

The aim of this book is to present fundamentals of algebraic specifications with respect to the following three aspects: fundamentals in the sense of a carefully motivated introduction to algebraic specifications, which is easy to understand for computer scientists and mathematicians; fundamentals in the sense of mathematical theories which are the basis for precise definitions, constructions, results, and correctness proofs; and fundamentals in the sense of concepts, which are introduced on a conceptual level and formalized in mathematical terms. The book is equally suitableas a text book for graduate courses and as a reference for researchers and system developers.

Combinatory logic started as a programme in the foundation of mathematics and in an historical context at a time when such endeavours attracted the most gifted among the mathematicians. This small volume arose under quite differ ent circumstances, namely within the context of reworking the mathematical foundations of computer science. I have been very lucky in finding gifted students who agreed to work with me and chose, for their Ph. D. theses, subjects that arose from my own attempts 1 to create a coherent mathematical view of these foundations. The result of this collaborative work is presented here in the hope that it does justice to the individual contributor and that the reader has a chance of judging the work as a whole. E. Engeler ETH Zurich, April 1994 lCollected in Chapter III, An Algebraization of Algorithmics, in Algorithmic Properties of Structures, Selected Papers of Erwin Engeler, World Scientific PubJ. Co., Singapore, 1993, pp. 183-257. I Historical and Philosophical Background Erwin Engeler In the fall of 1928 a young American turned up at the Mathematical Institute of Gottingen, a mecca of mathematicians at the time; he was a young man with a dream and his name was H. B. Curry. He felt that he had the tools in hand with which to solve the problem of foundations of mathematics mice and for all. His was an approach that came to be called "formalist" and embodied that later became known as Combinatory Logic."

This book constitutes the thoroughly refereed post-conference proceedings of the 15th International SDL Forum, SDL 2011, held in Toulouse, France, in July 2011. The 16 revised full papers presented together were carefully reviewed and selected for inclusion in the book. The papers cover a wide range of topics such as SDL and related languages; testing; and services and components to a wide range presentations of domain specific languages and applications, going from use maps to train station models or user interfaces for scientific dataset editors for high performance computing.