Peter Ruzicka – författare

Preface Due to the development of hardware technologies (such as VLSI) in the early 1980s, the interest in parallel and distributive computing has been rapidly growingandinthelate1980sthestudyofparallelalgorithmsandarchitectures became one of the main topics in computer science. To bring the topic to educatorsandstudents,severalbooksonparallelcomputingwerewritten. The involvedtextbook“IntroductiontoParallelAlgorithmsandArchitectures”by F. Thomson Leighton in 1992 was one of the milestones in the development of parallel architectures and parallel algorithms. But in the last decade or so the main interest in parallel and distributive computing moved from the design of parallel algorithms and expensive parallel computers to the new distributive reality – the world of interconnected computers that cooperate (often asynchronously) in order to solve di?erent tasks. Communication became one of the most frequently used terms of computer science because of the following reasons: (i) Considering the high performance of current computers, the communi- tion is often moretime consuming than the computing time of processors. As a result, the capacity of communication channels is the bottleneck in the execution of many distributive algorithms. (ii) Many tasks in the Internet are pure communication tasks. We do not want to compute anything, we only want to execute some information - change or to extract some information as soon as possible and as cheaply as possible. Also, we do not have a central database involving all basic knowledge. Instead, wehavea distributed memorywherethe basickno- edgeisdistributedamongthelocalmemoriesofalargenumberofdi?erent computers. The growing importance of solving pure communication tasks in the - terconnected world is the main motivation forwriting this book.

Preface Due to the development of hardware technologies (such as VLSI) in the early 1980s, the interest in parallel and distributive computing has been rapidly growingandinthelate1980sthestudyofparallelalgorithmsandarchitectures became one of the main topics in computer science. To bring the topic to educatorsandstudents,severalbooksonparallelcomputingwerewritten. The involvedtextbook“IntroductiontoParallelAlgorithmsandArchitectures”by F. Thomson Leighton in 1992 was one of the milestones in the development of parallel architectures and parallel algorithms. But in the last decade or so the main interest in parallel and distributive computing moved from the design of parallel algorithms and expensive parallel computers to the new distributive reality – the world of interconnected computers that cooperate (often asynchronously) in order to solve di?erent tasks. Communication became one of the most frequently used terms of computer science because of the following reasons: (i) Considering the high performance of current computers, the communi- tion is often moretime consuming than the computing time of processors. As a result, the capacity of communication channels is the bottleneck in the execution of many distributive algorithms. (ii) Many tasks in the Internet are pure communication tasks. We do not want to compute anything, we only want to execute some information - change or to extract some information as soon as possible and as cheaply as possible. Also, we do not have a central database involving all basic knowledge. Instead, wehavea distributed memorywherethe basickno- edgeisdistributedamongthelocalmemoriesofalargenumberofdi?erent computers. The growing importance of solving pure communication tasks in the - terconnected world is the main motivation forwriting this book.

SOFSEM 2001, the International Conference on Current Trends in Theory and Practice of Informatics, was held on November 24 – December 1, 2001 in the ? well-known spa Pie?stany, Slovak Republic. This was the 28th annual conference in the SOFSEM series organized either in the Slovak or the Czech Republic. SOFSEM has a well-established tradition. Currently it is a broad, multid- ciplinary conference, devoted to the theory and practice of software systems. Its aim is to foster cooperation among professionals from academia and industry working in various areas of informatics. The scienti?c program of SOFSEM consists of invited talks, which determine the topics of the conference, and short contributed talks presenting original - sults. The topics of the invited talks are chosen so as to cover the whole range from theory to practice and to bring interesting research areas to the attention of conference participants. For the year 2001, the following three directions were chosen for presentation by the SOFSEM Steering Committee: – Trends in Informatics – Enabling Technologies for Global Computing – Practical Systems Engineering and Applications The above directions were covered through 12 invited talks presented by pro- nent researchers. There were 18 contributed talks, selected by the international Program Committee from among 46 submitted papers. The conference was also accompanied by workshops on Electronic Commerce Systems (coordinated by H. D. Zimmermann) and Soft Computing (coordinated by P. H´ajek).

SOFSEM 2001, the International Conference on Current Trends in Theory and Practice of Informatics, was held on November 24 – December 1, 2001 in the ? well-known spa Pie?stany, Slovak Republic. This was the 28th annual conference in the SOFSEM series organized either in the Slovak or the Czech Republic. SOFSEM has a well-established tradition. Currently it is a broad, multid- ciplinary conference, devoted to the theory and practice of software systems. Its aim is to foster cooperation among professionals from academia and industry working in various areas of informatics. The scienti?c program of SOFSEM consists of invited talks, which determine the topics of the conference, and short contributed talks presenting original - sults. The topics of the invited talks are chosen so as to cover the whole range from theory to practice and to bring interesting research areas to the attention of conference participants. For the year 2001, the following three directions were chosen for presentation by the SOFSEM Steering Committee: – Trends in Informatics – Enabling Technologies for Global Computing – Practical Systems Engineering and Applications The above directions were covered through 12 invited talks presented by pro- nent researchers. There were 18 contributed talks, selected by the international Program Committee from among 46 submitted papers. The conference was also accompanied by workshops on Electronic Commerce Systems (coordinated by H. D. Zimmermann) and Soft Computing (coordinated by P. H´ajek).

This volume constitutes the proceedings of the 19th International Symposium on Mathematical Foundations of Theoretical Computer Science, MFCS '94, held in Kosice, Slovakia in August 1994.MFCS '94 brought together specialists in theoretical fields of computer science from various countries in order to stimulate mathematical research in theoretical computer science. Besides 12 papers based on invited talks by renowned experts, the book contains 42 research contributions selected from a total of 112 submissions. All areas of theoretical computer science are presented, some from a particular mathematical point of view.

This book constitutes the refereed proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS '97, held in Bratislava, Slovakia, in August 1997.The 40 revised full papers presented were carefully selected from a total of 94 submissions. Also included are nine invited papers and two abstracts of invited talks. The papers cover the whole range of theoretical computer science including programming theory, complexity theory, mathematical logic, rewriting, grammars, formal languages, theory of algorithms, computational graph theory, etc.