Volker Diekert Livres

This volume presents the lecture notes from the authors’ three summer courses offered during the program “Automorphisms of Free Groups: Geometry, Topology, and Dynamics,” held at the Centre de Recerca Matemàtica (CRM) in Bellaterra, Spain. The first two chapters present the basic tools needed, from formal language theory (regular and context-free languages, automata, rewriting systems, transducers, etc) and emphasize their connections to group theory, mostly relating to free and virtually-free groups. The material covered is sufficient to present full proofs of many of the existing interesting characterizations of virtually-free groups. In turn, the last chapter comprehensively describes Bonahon’s construction of Thurston’s compactification of Teichmüller space in terms of geodesic currents on surfaces. It also includes several intriguing extensions of the notion of geodesic current to various other, more general settings.

The idea behind this book is to provide the mathematical foundations for assessing modern developments in the Information Age. It deepens and complements the basic concepts, but it also considers instructive and more advanced topics. The treatise starts with a general chapter on algebraic structures; this part provides all the necessary knowledge for the rest of the book. The next chapter gives a concise overview of cryptography. Chapter 3 on number theoretic algorithms is important for developping cryptosystems, Chapter 4 presents the deterministic primality test of Agrawal, Kayal, and Saxena. The account to elliptic curves again focuses on cryptographic applications and algorithms. With combinatorics on words and automata theory, the reader is introduced to two areas of theoretical computer science where semigroups play a fundamental role. The last chapter is devoted to combinatorial group theory and its connections to automata. Contents: Algebraic structures Cryptography Number theoretic algorithms Polynomial time primality test Elliptic curves Combinatorics on words Automata Discrete infinite groups

Die Vielzahl der Beiträge in diesem Band zum 65. Geburtstag von Volker Claus spiegelt die Breite seines Wirkens und die Anerkennung wider, die er in seinem Fachgebiet genießt. Ich kenne ihn seit seiner gemeinsamen Zeit mit Heidemone Böhle, als sie sich über die Anforderungen der Vordiplomsprüfung in angewandter Mathematik informierten. Beide bestanden diese Prüfung vor dem vierten Semester und verbanden mehr als nur das Studium, da sie später ein glückliches Ehepaar wurden. Claus' Diplomarbeit, Dissertation und die Publikationen, die zu seiner Habilitation 1972 führten, behandelten Probleme der theoretischen Informatik. Bevor das Verfahren abgeschlossen wurde, folgte er einem Ruf an die Universität Dortmund, über dessen Tätigkeit in einem der Beiträge ausführlicher berichtet wird. In Saarbrücken engagierte sich Claus auch stark in hochschulpolitischen Belangen. Meine damalige Einschätzung seiner Person spiegelt sich in verschiedenen Gutachten wider: Er erweist sich als vielseitiger Informatiker, dessen Arbeiten wesentliche Fragen der Informatik betreffen. Seine Texte sind klar, die Beweise exakt und seine Literaturkenntnis hervorragend. Zudem ist er didaktisch geschickt, ausdauernd und schnell in seiner Arbeit und zeigt sich offen für neue Fragestellungen, in die er sich rasch einarbeitet.

The book features a diverse range of topics, including invited talks and regular papers. It covers various aspects of formal languages and automata theory, such as factorization forests, weighted versus probabilistic logics, and the post correspondence problem. Key discussions include the size complexity of two-way finite automata, matrix mortality, and the ? erný-Pin conjecture. The text delves into synchronizing words in one-cluster automata, majority quantifiers in regular languages, and the inclusion problem of context-free languages. It also addresses the complexity of avoiding sets of partial words and explores closures in formal languages. Additional topics include rich and periodic-like words, traces of control-flow graphs, and synchronous relations. The book extends the Lyndon-Schützenberger result to pseudoperiodic words and examines strongly regular grammars. It discusses powers of regular languages, descriptive patterns, and stateless multihead finite automata. The work also touches on crucial words for abelian powers, descriptional complexity of regular expressions, and the pumping lemma for well-nested multiple context-free languages. Further insights include game-theoretic characterizations of Boolean grammars, word equations, and limitations of equations over sets of numbers. The text also presents a weighted ?-calculus, branching-time temporal logics, and simulations by time-bounded counter machines, alongs

The content explores various advanced topics in computer science and mathematics, including the limits of quantum computing, formal verification of microprocessors, and the intersection of language and data structures. It addresses complex issues such as the decidability of parameterized probabilistic information flow, challenges in constraint satisfaction problems, and the intricacies of path packing algorithms. The work also delves into the theory of conjunctive grammars, the complexity of matrix rank, and the application of modified colored Petri nets for protocol verification. Additionally, it discusses the performance modeling of networks, efficient computation in groups, and the implications of Kolmogorov complexity. The annotation highlights the significance of empirical randomness, the development of algorithms for zero-testing polynomials, and the exploration of unique matchings and equivalence problems in circuit design. The research emphasizes innovative approaches to clustering, image retrieval, and the mathematical foundations underlying various computational theories. Overall, the content presents a comprehensive overview of contemporary challenges and methodologies in the fields of computer science and discrete mathematics.

The content covers a range of topics in computer science and mathematics, focusing on algorithmic complexity, combinatorics, and automata theory. It includes invited talks on automorphisms of finite rings, algebraic generating functions, and algorithmics in exponential time. The sessions delve into worst-case and average-case approximations, sampling problems, and scheduling mechanisms. Further discussions explore counting in guarded logic, the variable hierarchy of the ?-calculus, and the universality of cellular automata. Decidability of temporal properties in probabilistic automata and contract-signing protocols are also examined. The complexity of various problems, including polylog-time reductions and optimal algorithms for colored balls, is addressed, alongside cost-sharing mechanisms in set cover games. Additional topics include dynamic complexity theory, minimal Bézout numbers, and the shortest monotone descent path problem. The sessions also cover quantified constraint satisfaction, connectivity for wireless agents, and topological automata. Information theory in property testing and the complexity of solving linear equations over finite rings are highlighted, along with advancements in quantum algorithms and sorting techniques. The content concludes with discussions on minimum cycle bases in directed graphs and automatic presentations for finitely generated groups, showcasing a comprehensive exploration of contem

The Symposium on Theoretical Aspects of Computer Science (STACS) is alt- nately held in France and in Germany. The conference of March 25-27, 2004 at the Corum, Montpellier was the twenty-?rst in this series. Previous meetings took place in Paris (1984), Saarbruc ] ken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wurzburg ] (1993), Caen(1994), Munc ] hen(1995), Grenoble(1996), Lub ] eck (1997), Paris (1998), Trier (1999), Lille (2000), Dresden (2001), Antibes (2002), and Berlin (2003). The symposium looks back at a remarkable tradition of over 20 years. The interest in STACS has been increasing continuously during recent years and has turned it into one of the most signi?cant conferences in theoretical computer science. The STACS 2004 call for papers led to more than 200 submissions from all over the world. morethan800reviewsweredone. We would like to thank the program committee and all external referees for the valuable work they put into the reviewing process of this conference. We had a two-day meeting for the program committee in Montpellier during November 21-22, 2003. Just 54 papers (i.e., 27% of the submissions) could be accepted, as we wanted to keep the conference in its standard format with only two parallel sessions. This strict selection guaranteed the very high scienti?c quality of the conference.

Diskrete algebraische Methoden sind ein zukunftsweisendes Gebiet, dessen Grundlagen zunehmend an Bedeutung gewinnen. Dieses Lehrbuch vermittelt wesentliche Elemente der diskreten Mathematik, um moderne Entwicklungen im Informationszeitalter mathematisch kompetent beurteilen zu können. Es beginnt mit einem Kapitel über algebraische Strukturen, das die Grundlage für das gesamte Buch bildet. Darauf folgt ein Kapitel zu Kryptographie und ein weiteres über zahlentheoretische Algorithmen, die für die Erzeugung von Kryptosystemen, insbesondere großer „zufälliger“ Primzahlen, wichtig sind. Kapitel 4 behandelt den deterministischen Polynomialzeittest von Agrawal, Kayal und Saxena zur Primzahlerkennung. Das nächste Kapitel zu elliptischen Kurven fokussiert auf zahlentheoretische und kryptographische Anwendungen. Mit den Kapiteln „Kombinatorik auf Wörtern“ und „Automatentheorie“ wird das Teilgebiet der theoretischen Informatik behandelt, in dem die Halbgruppentheorie zentral ist. Das letzte Kapitel widmet sich diskreten unendlichen Gruppen. Das Buch vertieft Grundlagen, zeigt Anwendungen auf und behandelt auch über den Standardstoff hinausgehende Themen. Aufgaben und Lösungen nehmen einen hohen Stellenwert ein, und zu allen wichtigen Aussagen werden vollständige Beweise geliefert. Am Ende jedes Kapitels finden sich kurze Zusammenfassungen als Lernhilfe. Es richtet sich an Masterstudierende der Mathematik und Informatik mit fortgeschritte

Die Grundidee des Lehrbuchs ist, wesentliche Elemente der diskreten Mathematik zu vermitteln, um moderne Entwicklungen im Informationszeitalter mathematisch beurteilen zu können. Dazu gehören das Verständnis von Graphen, das Rechnen mit großen Zahlen und modulo n. Die Autoren beginnen mit der elementaren Zahlentheorie und erläutern insbesondere die Verschlüsselung mit dem RSA-Verfahren. Es folgen Abschätzungen, die wichtig sind, um Objekte zu zählen oder Laufzeiten von Algorithmen zu verstehen. Zuverlässige Algorithmen nutzen den Zufall, weshalb ein Kapitel zur diskreten Wahrscheinlichkeit nicht fehlen darf. Anschließend wird die Kombinatorik, erzeugende Funktionen und Graphentheorie behandelt. Der Abschluss widmet sich Ordnungsstrukturen, Verbänden sowie booleschen Funktionen und Schaltkreisen. Das Buch vertieft Grundlagen und zeigt Anwendungen, behandelt aber auch über den Standardstoff hinausgehende Themen. Ein hoher Stellenwert wird Aufgaben und Lösungen eingeräumt, und für alle wichtigen Aussagen gibt es vollständige Beweise. Am Ende jedes Kapitels finden sich kurze Zusammenfassungen als Lernhilfe. Das benötigte Vorwissen ist gering, und die Grundlagen sind mehr als bloße Definitionen. Das Buch fördert ein tieferes Verständnis und vermittelt Techniken, die den Leser befähigen, selbstständig mathematische Probleme zu lösen.