Bücher der Reihe Theoretical Computer Science and General Issues

This book constitutes the thoroughly refereed post-proceedings of the 11th International Workshop on DNA Based Computers, DNA11, held in London, ON, Canada, in June 2005. The 34 revised full papers presented were carefully selected during two rounds of reviewing and improvement from an initial total of 79 submissions. The wide-ranging topics include in vitro and in vivo biomolecular computation, algorithmic self-assembly, DNA device design, DNA coding theory, and membrane computing.

This book constitutes the refereed proceedings of the First International Symposium on Computer Science in Russia, CSR 2006. The 35 revised full theory papers and 29 revised application papers together with 3 invited talks address all major areas in computer science are addressed. The theory track deals with algorithms, protocols, data structures and more. The application part comprises programming and languages; computer architecture and hardware design among many more topics.

This book constitutes the refereed proceedings of the 5th International Workshop on Experimental and Efficient Algorithms, WEA 2006, held in Menorca, Spain, May 2006. The book presents 26 revised full papers together with 3 invited talks. The application areas addressed include most fields applying advanced algorithmic techniques, such as combinatorial optimization, approximation, graph theory, discrete mathematics, scheduling, searching, sorting, string matching, coding, networking, and more.

This book constitutes the refereed proceedings of the 27th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, ICATPN 2006, held in Turku, Finland in June 2006. The book presents 16 revised full papers and 6 revised tool papers together with 4 invited papers. All current issues on research and development in the area of Petri nets and modeling of concurrent systems are addressed.

CiE 2006: Logical Approaches to Computational Barriers Swansea, Wales, June 30 - July 5, 2006 Computability in Europe (CiE) is an informal network of European scientists working on computability theory, including its foundations, technical devel- ment, and applications. Among the aims of the network is to advance our t- oretical understanding of what can and cannot be computed, by any means of computation. Its scienti?c vision is broad: computations may be performed with discrete or continuous data by all kinds of algorithms, programs, and - chines. Computations may be made by experimenting with any sort of physical system obeying the laws of a physical theory such as Newtonian mechanics, quantum theory or relativity. Computations may be very general, depending upon the foundations of set theory; or very speci?c, using the combinatorics of ?nite structures. CiE also works on subjects intimately related to computation, especially theories of data and information, and methods for formal reasoning about computations. The sources of new ideas and methods include practical developments in areas such as neural networks, quantum computation, natural computation, molecular computation, and computational learning. Applications are everywhere, especially, in algebra, analysis and geometry, or data types and programming. This volume, Logical Approaches to Computational Barriers, is the proce- ings of the second in a series of conferences of CiE that was held at the Depa- ment of Computer Science, Swansea University, 30 June - 5 July, 2006.

This book constitutes the refereed proceedings of the 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, held in Riga, Latvia, in July 2006. The proceedings includes 36 revised full papers presented together with 3 invited papers, addressing issues of theoretical algorithmics and applications in various fields including graph algorithms, computational geometry, scheduling, approximation algorithms, network algorithms, data storage and manipulation, combinatorics, sorting, searching, online algorithms, optimization, amd more.

This book constitutes the thoroughly refereed post-proceedings of the International Dagstuhl-Seminar on Architecting Systems with Trustworthy Components, held in Dagstuhl Castle, Germany, in December 2004. Presents 10 revised full papers together with 5 invited papers contributed by outstanding researchers. Discusses core problems in measurement and normalization of non-functional properties, modular reasoning over non-functional properties, capture of component requirements in interfaces and protocols, interference and synergy of top-down and bottom-up aspects, and more.

This book constitutes the refereed post-proceedings of the 9th International Conference on Principles of Distributed Systems, OPODIS 2005, held in Pisa, Italy in December 2005. The volume presents 30 revised full papers and abstracts of 2 invited talks. The papers are organized in topical sections on nonblocking synchronization, fault-tolerant broadcast and consensus, self-stabilizing systems, peer-to-peer systems and collaborative environments, sensor networks and mobile computing, security and verification, real-time systems, and peer-to-peer systems.

This book constitutes the refereed proceedings of the 9th International Conference on Theory and Applications of Satisfiability Testing, SAT 2006. The book presents 26 revised full papers together with 11 revised short papers and 2 invited talks. Coverage extends to all current research issues in propositional and quantified Boolean formula satisfiability testing. The papers are organized in topical sections on proofs and cores, heuristics and algorithms, and more.

ICARIS 2006 is the ?fth instance of a series of conferences dedicated to the comprehension and the exploitation of immunological principles through their translation into computational terms. All scienti?c disciplines carrying a name that begins with "e;arti?cial"e; (followed by "e;life,"e; "e;reality,"e; "e;intelligence"e; or "e;- munesystem"e;) aresimilarlysu?ering froma veryambiguousidentity.Their axis of research tries to stabilize an on-going identity somewhere in the crossroad of engineering (building useful artifacts), natural sciences (biologyor psychology- improving the comprehension and prediction of natural phenomena) and t- oretical computer sciences (developing and mastering the algorithmic world). Accordingly and depending on which of these perspectives receives more s- port, they attempt at attracting di?erent kinds of scientists and at stimul- ing di?erent kinds of scienti?c attitudes. For many years and in the previous ICARIS conferences, it was clearly the "e;engineering"e; perspective that was the most represented and prevailed through the publications. Indeed, since the o- gin of engineering and technology, nature has o?ered a reserve of inexhaustible inspirations which have stimulated the development of useful artifacts for man. Biology has led to the development of new computer tools, such as genetic - gorithms, Boolean and neural networks, robots learning by experience, cellular machines and others that create a new vision of IT for the engineer: parallel, ?exible andautonomous.Inthis type of informatics,complexproblemsareta- led with the aid of simple mechanisms, but in?nitely iterated in time and space.

This book constitutes the refereed proceedings of the 14th Annual European Symposium on Algorithms, ESA 2006, held in Zurich, Switzerland, in the context of the combined conference ALGO 2006. The book presents 70 revised full papers together with abstracts of 3 invited lectures. The papers address all current subjects in algorithmics, reaching from design and analysis issues of algorithms over to real-world applications and engineering of algorithms in various fields.

The Second International Workshop on Parameterized and Exact Computation (IWPEC) was held in Zu *rich, Switzerland, during September 13-15, 2006. It th was organized as a component of ALGO 2006, which also hosted the 14 - th nual European Symposium on Algorithms, the 6 Workshop on Algorithms in th Bioinformatics, the 4 Workshop on Approximation and Online Algorithms, th and the 6 Workshop on Algorithmic Methods and Models for Optimization of Railways. This meeting was the second in the IWPEC series, with the ?rst having been held in Bergen, Norway, during September 14-16, 2004. The ?eld continues to experience rapid growth, in part due to its appeal as an alternative to tra- tional complexity theory, and in part due to the powerful practical applications it has spawned. IWPEC events are intended to cover research in all aspects of parameterizedand exact computation and complexity, including but not limited to new techniques for the design and analysis of parameterized and exact al- rithms, parameterized complexity theory, relationships between parameterized complexity and traditional complexity, applications of parameterized and exact computation, implementation issues and high-performance computing. A major goal is to disseminate the latest research results, including signi?cant work-- progress, and to identify, de?ne and explore directions for future study. The papers accepted for presentation and printed in these proceedings rep- sent a diverse spectrum of the latest developments on parameterized and exact algorithm design, analysis, application and implementation.

This book constitutes the refereed proceedings of the 4th International Conference on Sequences and Their Applications, SETA 2006. The book presents 32 revised full papers together with 4 invited lectures. The papers are organized in topical sections on linear complexity of sequences, correlation of sequences, stream ciphers and transforms, topics in complexities of sequences, multi-sequence synthesis, sequences and combinatorics, FCSR sequences, aperiodic correlation and applications, and boolean functions, and more.

DISC, the International Symposium on DIStributed Computing, is an annual forum for presentation of research on all facets of distributed computing, inc- ding the theory, design, analysis, implementation, and application of distributed systems and networks. The 20th anniversary edition of DISC was held on S- tember 18-20, 2006, in Stockholm, Sweden. There were 145 extended abstracts submitted to DISC this year, and this - lume contains the 35 contributions selected by the Program Committee and one invited paper among these 145 submissions. All submitted papers were read and evaluated by at least three Program Committee members, assisted by external reviewers. The ?nal decision regarding every paper was taken during the P- gram Committee meeting, which took place in Beer-Sheva, June 30 and July 1, 2006. The Best Student Award was split and given to two papers: the paper "e;- act Distance Labelings Yield Additive-Stretch Compact Routing Schemes,"e; by Arthur Bradly, and Lenore Cowen, and the paper "e;A Fast Distributed App- ximation Algorithm for Minimum Spanning Trees"e; co-authored by Maleq Khan and Gopal Pandurangan. The proceedings also include 13 three-page-long brief announcements (BA). TheseBAsarepresentationsofongoingworksforwhichfullpapersarenotready yet, or of recent results whose full description will soon be or has been recently presented in other conferences. Researchers use the BA track to quickly draw the attention of the community to their experiences, insights and results from ongoing distributed computing research and projects. The BAs included in this proceedings volume were selected among 26 BA submissions.

This volume contains the papers presented at the 13th International Symposium on String Processing and Information Retrieval (SPIRE), held October 11-13, 2006, in Glasgow, Scotland. The SPIRE annual symposium provides an opportunity for both new and established researchers to present original contributions to areas such as string processing (dictionary algorithms, text searching, pattern matching, text c- pression, text mining, natural language processing, and automata-based string processing); information retrieval languages, applications, and evaluation (IR modelling, indexing, ranking and ?ltering, interface design, visualization, cro- lingual IR systems, multimedia IR, digital libraries, collaborative retrieval, W- related applications, XML, information retrieval from semi-structured data, text mining, and generation of structured data from text); and interaction of biology and computation (sequencing and applications in molecular biology, evolution and phylogenetics, recognition of genes and regulatory elements, and sequen- driven protein structure prediction). The papers in this volume were selected from 102 papers submitted from over 20 di?erent countries in response to the Call for Papers. A total of 26 submissions were accepted as full papers, yielding an acceptance rate of about 25%. In view of the large number of good-quality submissions the Program Committee decided to accept 5 short papers, that have also been included in the proceedings. SPIRE 2006 also featured two talks by invited speakers: Jamie Callan (Carnegie Mellon University, USA) and Martin Farach-Colton (Rutgers University, USA).