Bücher der Reihe Theoretical Computer Science and General Issues

We wish to extend a warm welcome to the reader of this extended postp- ceedings publication of SAG 2004, the 1st International Workshop on Scienti?c Applications on Grid Computing. This workshop was held in September 2004, in conjunction with the 2004 IEEE/WIC/ACM International Joint Conference on Web Intelligence (WI 2004) and Intelligent Agent Technology (IAT 2004). The WI and IAT conferences have provided, for several years, a leading - ternational forum to bring together researchers and practitioners from diverse ?elds,suchascomputerscience,informationtechnology,business,education,- man factors, systems engineering, and robotics, to explore the fundamental roles as well as practical impacts of arti?cial intelligence (AI) (e.g., knowledge r- resentation, planning, knowledge discovery, and data mining, intelligent agents and social network intelligence) and advanced information technology (IT) (e.g., wireless networks, ubiquitous devices, social networks, the Wisdom Web, and data/knowledge grids), and to examine the design principles and performance characteristics of various approaches in intelligent agent technology.

This volume contains the refereed proceedings of the 3rd International Conf- ence on Sequences and Their Applications (SETA 2004), held in Seoul, Korea during October 24-28, 2004. The previous two conferences, SETA 1998 and SETA 2001, were held in Singapore and Bergen, Norway, respectively. These conferences are motivated by the many widespread applications of sequences in modern communication systems. These applications include pseudorandom sequences in spread spectrum systems, code-division multiple-access, stream ciphers in cryptography and several connections to coding theory. The Technical Program Committee of SETA 2004 received 59 submitted - pers, many more than the submissions to previous SETA conferences. The C- mittee therefore had the di?cult task of selecting the 33 papers to be presented at the Conference in addition to four invited papers. The authors of papers p- sented at the conference were invited to submit full papers that were refereed before appearing in this proceedings. These proceedings have been edited by the Co-chairs of the Technical P- gram Committee for SETA 2004: Tor Helleseth of the University of Bergen, Norway, and Dilip Sarwate of the University of Illinois at Urbana-Champaign, USA, and Technical Program Committee members Hong-Yeop Song of Yonsei University, Korea, and Kyeongcheol Yang of Pohang University of Science and Technology, Korea.

VECPAR is a series of international conferences dedicated to the promotion and advancement of all aspects of high-performance computing for computational science, as an industrial technique and academic discipline, extending the fr- tier of both the state of the art and the state of practice. The audience for and participants in VECPAR are seen as researchers in academic departments, g- ernment laboratories and industrial organizations. There is now a permanent website for the series, http://vecpar.fe.up.pt, where the history of the conf- ences is described. ThesixtheditionofVECPARwasthe?rsttimetheconferencewascelebrated outside Porto - at the Universitad Politecnica de Valencia (Spain), June 28-30, 2004. The whole conference programme consisted of 6 invited talks, 61 papers and26posters,outof130contributionsthatwereinitiallysubmitted.Themajor themes were divided into large-scale numerical and non-numerical simulations, parallel and grid computing, biosciences, numerical algorithms, data mining and visualization. This postconference book includes the best 48 papers and 5 invited talks presented during the three days of the conference. The book is organized into 6 chapters, with a prominent position reserved for the invited talks and the Best Student Paper. As a whole it appeals to a wide research community, from those involved in the engineering applications to those interested in the actual details of the hardware or software implementations, in line with what, in these days, tends to be considered as computational science and engineering (CSE).

This book constitutes the refereed proceedings of the 12th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2005, held in Mont Saint-Michel, France in May 2005.The 22 revised full papers presented were carefully reviewed and selected from 48 submissions. The papers address issues such as topics in distributed and parallel computing, information dissemination, communication complexity, interconnection networks, high speed networks, wireless networking, mobile computing, optical computing, and related areas.

The 2nd International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR2005)washeldinPrague,CzechRepublic,duringMay31-June1,2005. The conference is intended primarily as a forum to focus on the integration and hybridization of the approaches of constraint programming (CP), arti?cial intelligence (AI), and operations research (OR) technologies for solving large-scale and complex real-life optimization problems. Therefore, CPAIOR is never far from industrial applications. The high number of submissions received this year, almost 100 papers, in witness to the interest of the research community in this conference. From these submissions, we chose 26 to be published in full in the proceedings. This volume includes summaries of the invited talks of CPAIOR: one from industry, one from the embedded system research community, and one from the operations research community. The invited speakers were: Filippo Focacci from ILOGS.A.,France,oneoftheleadingcompaniesinthe?eld;PaulPop,professor in the Embedded Systems Lab in the Computer and Information Science - partment, Link* oping University; and Paul Williams, full professor of Operations Research at the London School of Economics. The day before CPAIOR, a Master Class was organized by Gilles Pesant, where leading researchers gave introductory and overview talks in the area of metaheuristics and constraint programming. The Master Class was intended for PhD students, researchers, and practitioners. We are very grateful to Gilles who brought this excellent program together. For conference publicity we warmly thank Willem Jan van Hoeve and Petr Vil' ?m who did a great job with the high number of submissions received.

The8thWorkshopontheFoundationsofGeneticAlgorithms,FOGA-8,washeld at the University of Aizu in Aizu-Wakamatsu City, Japan, January 5-9, 2005. This series of workshops was initiated in 1990 to encourage further research on the theoretical aspects of genetic algorithms, and the workshops have been held biennially ever since. The papers presented at these workshops are revised, edited and published as volumes during the year following each workshop. This series of (now eight) volumes provides an outstanding source of reference for the theoretical work in this ?eld. At the same time this series of volumes provides a clear picture of how the theoretical research has grown and matured along with the ?eld to encompass many evolutionary computation paradigms including evolution strategies (ES), evolutionary programming (EP), and genetic programming (GP), as well as the continuing growthininteractionswith other ?elds suchas mathematics,physics, and biology. Atraditionoftheseworkshopsisorganizetheminsuchawayastoencourage lots of interaction and discussion by restricting the number of papers presented and the number of attendees, and by holding the workshop in a relaxed and informal setting. This year's workshop was no exception. Thirty-two researchers met for 3 days to present and discuss 16 papers. The local organizer was Lothar Schmitt who, together with help and support from his university, provided the workshop facilities. Aftertheworkshopwasover,theauthorsweregiventheopportunitytorevise their papers based on the feedback they received from the other participants.

The 8th International Conference on Theory and Applications of Satis?ability Testing(SAT2005)providedaninternationalforumforthemostrecentresearch on the satis?ablity problem (SAT). SAT is the classic problem of determining whether or not a propositional formula has a satisfying truth assignment. It was the ?rst problem shown by Cook to be NP-complete. Despite its seemingly specialized nature, satis?ability testing has proved to extremely useful in a wide range of di?erent disciplines, both from a practical as well as from a theoretical point of view. For example, work on SAT continues to provide insight into various fundamental problems in computation, and SAT solving technology has advanced to the point where it has become the most e?ective way of solving a number of practical problems. The SAT series of conferences are multidisciplinary conferences intended to bring together researchers from various disciplines who are interested in SAT. Topics of interest include, but are not limited to: proof systems and proof c- plexity; search algorithms and heuristics; analysis of algorithms; theories beyond the propositional; hard instances and random formulae; problem encodings; - dustrial applications; solvers and other tools. This volume contains the papers accepted for presentation at SAT 2005. The conference attracted a record number of 73 submissions. Of these, 26 papers were accepted for presentation in the technical programme. In addition, 16 - pers were accepted as shorter papers and were presented as posters during the technicalprogramme.Theacceptedpapersandposterpaperscoverthefullrange of topics listed in the call for papers.

The 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) was held in Lisbon, Portugal from July 11 to July 15, 2005. These proceedings contain all contributed papers presented at ICALP 2005, - getherwiththepapersbytheinvitedspeakersGiuseppeCastagna(ENS),Leonid Libkin (Toronto), John C. Mitchell (Stanford), Burkhard Monien (Paderborn), and Leslie Valiant (Harvard). The program had an additional invited lecture by Adi Shamir (Weizmann Institute) which does not appear in these proceedings. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS). The ?rst ICALP took place in 1972. This year, the ICALP program consisted of the established track A (focusing on algorithms, automata, complexity and games) and track B (focusing on logic, semantics and theory of programming), and innovated on the structure of its traditional scienti?c program with the inauguration of a new track C (focusing on security and cryptography foundation). In response to a call for papers, the Program Committee received 407 s- missions, 258 for track A, 75 for track B and 74 for track C. This is the highest number of submitted papers in the history of the ICALP conferences. The P- gram Committees selected 113 papers for inclusion in the scienti?c program. In particular, the Program Committee for track A selected 65 papers, the P- gram Committee for track B selected 24 papers, and the Program Committee for track C selected 24 papers. All the work of the Program Committees was done electronically.

Nowadays, developers have to face the proliferation of hardware and software environments, the increasing demands of the users, the growing number of p- grams and the sharing of information, competences and services thanks to the generalization ofdatabasesandcommunication networks. Aprogramisnomore a monolithic entity conceived, produced and ?nalized before being used. A p- gram is now seen as an open and adaptive frame, which, for example, can - namically incorporate services not foreseen by the initial designer. These new needs call for new control structures and program interactions. Unconventionalapproachestoprogramminghavelongbeendevelopedinv- iousnichesandconstituteareservoirofalternativewaystofacetheprogramming languages crisis. New models of programming (e. g. , bio-inspired computing, - ti?cialchemistry,amorphouscomputing,. . . )arealsocurrentlyexperiencinga renewed period of growth as they face speci?c needs and new application - mains. These approaches provide new abstractions and notations or develop new ways of interacting with programs. They are implemented by embedding new sophisticated data structures in a classical programming model (API), by extending an existing language with new constructs (to handle concurrency, - ceptions, open environments, . . . ), by conceiving new software life cycles and program executions (aspect weaving, run-time compilation) or by relying on an entire new paradigm to specify a computation. They are inspired by theoretical considerations (e. g. , topological, algebraic or logical foundations), driven by the domain at hand (domain-speci?c languages like PostScript, musical notation, animation, signal processing, etc. ) or by metaphors taken from various areas (quantum computing, computing with molecules, information processing in - ological tissues, problem solving from nature, ethological and social modeling).

The flying machines proposed by Leonardo da Vinci in the fifteenth century, the se- reproducing automata theory proposed by John von Neumann in the middle of the twentieth century and the current possibility of designing electronic and mechanical systems using evolutionary principles are all examples of the efforts made by humans to explore the mechanisms present in biological systems that permit them to tackle complex tasks. These initiatives have recently given rise to the emergent field of b- inspired systems and evolvable hardware. The inaugural workshop, Towards Evolvable Hardware, took place in Lausanne in October 1995, followed by the successive events of the International Conference on Evolvable Systems: From Biology to Hardware, held in Tsukuba (Japan) in October 1996, in Lausanne (Switzerland) in September 1998, in Edinburgh (UK) in April 2000, in Tokyo (Japan) in October 2001, and in Trondheim (Norway) in March 2003. Following the success of these past events the sixth international conference was aimed at presenting the latest developments in the field, bringing together researchers who use biologically inspired concepts to implement real systems in artificial intelligence, artificial life, robotics, VLSI design, and related domains. The sixth conference consolidated this biennial event as a reference meeting for the community involved in bio-inspired systems research. All the papers received were reviewed by at least three independent reviewers, thus guaranteeing a high-quality bundle for ICES 2005.

This volume is the first part of the two-volume proceedings of the International C- ference on Artificial Neural Networks (ICANN 2005), held on September 11-15, 2005 in Warsaw, Poland, with several accompanying workshops held on September 15, 2005 at the Nicolaus Copernicus University, Toru , Poland. The ICANN conference is an annual meeting organized by the European Neural Network Society in cooperation with the International Neural Network Society, the Japanese Neural Network Society, and the IEEE Computational Intelligence Society. It is the premier European event covering all topics concerned with neural networks and related areas. The ICANN series of conferences was initiated in 1991 and soon became the major European gathering for experts in those fields. In 2005 the ICANN conference was organized by the Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland, and the Nicolaus Copernicus Univ- sity, Toru , Poland. From over 600 papers submitted to the regular sessions and some 10 special c- ference sessions, the International Program Committee selected - after a thorough peer-review process - about 270 papers for publication. The large number of papers accepted is certainly a proof of the vitality and attractiveness of the field of artificial neural networks, but it also shows a strong interest in the ICANN conferences.