Klaus W. Wagner – författare

Diese kompakte Einführung in die Theoretische Informatik stellt die wichtigsten Modelle für zentrale Probleme der Informatik vor. Dabei werden u.a. folgende Fragestellungen behandelt:Welche Probleme sind algorithmisch lösbar? (Theorie der Berechenbarkeit und Entscheidbarkeit)Wie schwierig ist es algorithmische Probleme zu lösen? (Theorie der Berechnungskomplexität, NP-Theorie)Wie sind informationsverarbeitende Systeme prinzipiell aufgebaut? (Theorie der endlichen Automaten)Welche Strukturen besitzen Programmiersprachen? (Theorie der formalen Sprachen)In der Erarbeitung dieser Themen wird der Abstraktionsprozeß von den realen Gegenständen der Informatik zu den in der Theoretischen Infromatik etabliertern Modellen, wie z.B. Random-Access-Maschinen, Turingmaschinen und endliche Automaten, nachvollzogen und umgekehrt verdeutlicht, was diese Modelle aufgrund der über sie gewonnenen Erkenntnisse für die Praxis leisten können.

This volume contains the proceedings of the tenth annualSymposium on Theoretical Aspects of Computer Science (STACS'93), held in W}rzburg, February 25-27, 1993.The STACS symposia are held alternately in Germany andFrance, and organized jointly by the Special Interest Groupfor Theoretical Computer Science of the Gesellschaft f}rInformatik (GI) and theSpecial Interest Group for AppliedMathematics of the Association Francaise des Sciences etTechnologies de l'Information et des Syst mes (afcet).The volume includes the three invited talks which opened thethree days of the symposium: "Causal and distributedsemantics for concurrent processes" (I. Castellani),"Parallel architectures: design and efficient use" (B.Monien et al.), and "Transparent proofs" (L. Babai). Theselection of contributed papers is organized into parts on:computational complexity, logic in computer science,efficient algorithms, parallel and distributed computation,language theory, computational geometry, automata theory,semantics and logic of programming languages, automatatheory and logic, circuit complexity, omega-automata,non-classical complexity, learning theory and cryptography,and systems.

This volume constitutes the proceedings of the 11th annual Symposium on Theoretical Aspects of Computer Science (STACS '94), held in Caen, France, February 24-26, 1994. Besides three prominent invited papers, the proceedings contains 60 accepted contributions chosen by the international program committee during a highly competitive reviewing process from a total of 234 submissions for 38 countries. The volume competently represents most areas of theoretical computer science with a certain emphasis on (parallel) algorithms and complexity.

The 4th International Computer Science Symposium in Russia (CSR 2009) was held August 18-23,2009 in Novosibirsk,Russia, hosted by the Sobolev Institute of Mathematics and Novosibirsk State University. It was the fourth event in the series of regular international meetings, following CSR 2006 in St. Petersburg, CSR 2007 in Ekaterinburg, and CSR 2008 in Moscow. The opening lecture was given by Andrei Voronkov, and four other invited plenary lectures were given by Sergei Odintsov, Wolfgang Thomas, Nikolai Vereshchagin, and Hongseok Yang. This volume contains all the accepted papers and some of the abstracts of the invited speakers. The scope of the proposed topics for the symposium was quite broad and covered basically all areas of computer science. We received 66 papers in total, and the Program Committee selected 29. Yandex provided the Best Student Paper Awards; the recepients of these awards were selected by the Program Committee: - Dmitry Itsykson, "Structural complexity of AvgBPP" - Yuri Pritykin and Julya Ulyashkina, "Aperiodicity measure for in?nite sequences." The reviewing processwasorganizedusing the EasyChairconferencesystem, created by Andrei Voronkov.We are grateful to our sponsors: - Russian Foundation for Basic Research - Yandex (the largest Russian Internet portal providing key Web services). We also thank the group of local organizers and in particular Pavel Salimov.