Volker Diekert - Böcker

This book constitutes the proceedings of the 26th International Conference on Developments in Language Theory, DLT 2022, which was held in Tampa, FL, USA, during May, 2022.

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 structuresCryptographyNumber theoretic algorithmsPolynomial time primality testElliptic curvesCombinatorics on wordsAutomataDiscrete infinite groups

This book treats the elements of discrete mathematics that have important applications in computer science, thus providing the necessary tools for the reader to come to a competent mathematical judgement of modern developments in the age of information. Almost all assertions are shown with full proofs. Exercises are provided, with solutions presented in full detail.

This book contains surveys and research articles on the state-of-the-art in finitely presented groups for researchers and graduate students. Overviews of current trends in exponential groups and of the classification of finite triangle groups and finite generalized tetrahedron groups are complemented by new results on a conjecture of Rosenberger and an approximation theorem. A special emphasis is on algorithmic techniques and their complexity, both for finitely generated groups and for finite Z-algebras, including explicit computer calculations highlighting important classical methods. A further chapter surveys connections to mathematical logic, in particular to universal theories of various classes of groups, and contains new results on countable elementary free groups. Applications to cryptography include overviews of techniques based on representations of p-groups and of non-commutative group actions. Further applications of finitely generated groups to topology and artificial intelligence complete the volume. All in all, leading experts provide up-to-date overviews and current trends in combinatorial group theory and its connections to cryptography and other areas.

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. Thereviewingprocesswasextremelyhard: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.

The Symposium on Theoretical Aspects of Computer Science (STACS) is alt- nately held in France and in Germany. The conference of February 24-26, 2005 inStuttgartwasthetwenty-secondinthisseries.Previousmeetingstookplacein 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), Berlin (2003), and Montpellier (2004). The interest in STACS has been increasing continuously during recent years and has turned it into a leading conference in theoretical computer science. The call for papers for STACS 2005 led to 217 submissions from all over the world. The 17 members of the Program Committee met in Stuttgart for two days at the end of October 2004 to select the contributions to be presented at the conference.Thanksareduetothecommitteeaswellastoalltheexternalreferees for their valuable work put into the reviewing process. Just 54 papers (i.e., 25% of the submissions) could be accepted, thus guaranteeing the very high scienti?c quality of the conference.Moreover, this strict selection enabled us to keep the conference in its standard format with only two parallel sessions. We would like to thank the three invited speakers Manindra Agrawal (Sin- pore), Mireille Bousquet-M' elou (Bordeaux), and Uwe Schoning .. (Ulm) for p- senting lectures and for their contributions to the proceedings. Finally we thank the local organizing committee and all members of the Institute of Formal Methods in Computer Science for their help. In particular wethankHolgerAustinat,HeikePhotien,andHorstProtefortheirgreate?orts.

Parallelism or concurrency is one of the fundamental concepts in computer science. But in spite of its importance, theoretical methods to handle concurrency are not yet sufficiently developed. This volume presents a comprehensive study of Mazurkiewicz' trace theory from an algebraic-combinatorial point of view. This theory is recognized as an important tool for a rigorous mathematical treatment of concurrent systems. The volume covers several different research areas, and contains not only known results but also various new results published nowhere else. Chapter 1 introduces basic concepts. Chapter 2 gives a straight path to Ochmanski's characterization of recognizable trace languages and to Zielonka's theory of asynchronous automata. Chapter 3 applies the theory of traces to Petri nets. A kind of morphism between nets is introduced which generalizes the concept of synchronization. Chapter 4 provides a new bridge between the theory of string rewriting and formal power series. Chapter 5 is an introduction to a combinatorial theory of rewriting on traces which can be used as an abstract calculus for transforming concurrent processes.

This book features the refereed proceedings of the 2nd International Symposium on Computer Science in Russia held in September 2007. The 35 papers cover theory track deals with algorithms, protocols, and data structures; complexity and cryptography; formal languages, automata and their applications to computer science; computational models and concepts; proof theory; and applications of logic to computer science. Many applications are presented.

Since 1993 the conference Developments in Language Theory (DLT) has been held in Europe every odd year and, since 2002, outside Europe every even year. The 13th conference in this series was DLT 2009. It took place in Stuttgart fromJune30to July3.PreviousmeetingsoccurredinTurku(1993),Magdeburg (1995),Thessaloniki(1997),Aachen(1999),Vienna(2001),Kyoto(2002),Szeged (2003), Auckland (2004), Palermo (2005), Santa Barbara (2006), Turku (2007), and Kyoto (2008). The DLT conference has developed into the main forum for language theory and related topics. This has also been re?ected in the high quality of the 70 s- missions received in 2009. Most submissions were reviewed by four Programme Committeemembersandtheirsub-referees.TheProgrammeCommitteeselected the best 35 papers for presentation during the conference. These 35 papers are also published in this proceedings volume. Members of the ProgrammeComm- tee were not allowed to submit papers. The work of the Programme Committee wasorganizedusingtheEasyChairconferencesystem,thankstoAndreiVoronkov. The conference programme included ?ve invited lectures.They were given by Mikola j Bojanczyk ' (Warsaw), Paul Gastin (Cachan), Tero Harju (Turku), ChristosKapoutsis(Nicosia),andBenjaminSteinberg(Ottawa).Wearegrateful to the invited speakers for accepting the invitation and presenting their lectures and for their contributions to the proceedings. The Informatik Forum Stuttgart provided a best paper award, which was selected by the Programme Committee. The recipient was: "Magic Numbers and Ternary Alphabet" by Galina Jiraskova.

Allein schon die Anzahl der Beiträge in diesem Band zum 65. Geburtstag von Volker Claus und ihre so unterschiedliche Thematik weist auf die Breite seines Wirkens und die Anerkennung hin, die er in seinem Wirkungsfeld erfährt. Ich k- ne ihn seit er zusammen mit Heidemone Böhle, zu mir kam, um sich darüber zu erkundigen, was man in der Prüfung zum Vordiplom in angewandter Mathematik alles zu wissen habe. Beide legten diese Prüfung noch vor dem vierten Semester ab. Beide verband aber mehr: Sie wurden später über lange Jahre ein glückliches Ehepaar. Die Diplomarbeit von Herrn Claus, seine Dissertation und die Publi- tionen, aufgrund deren er 1972 seine Habilitation angestoßen wurde, betrafen P- bleme der theoretischen Informatik. Bevor aber das Verfahren abgeschlossen war, die Gutachten lagen bereits vor, folgte er einem Ruf an die Universität Dortmund. Über seine Tätigkeit dort wird in einem der Beiträge in diesem Band ausführlicher berichtet. Herr Claus engagierte sich in Saarbrücken auch stark in hochschulpolitischen Fragen. Meine damalige Einschätzung seiner Person spiegelt sich wieder in v- schiedenen Gutachten, die ich über ihn schreiben musste und aus denen ich zitiere: • „Herr Claus erweist sich aufgrund seiner Arbeiten als vielseitiger Informa- ker. Seine Arbeiten betreffen wesentliche Fragen der Informatik. Die Arb- tensindsehrklargeschrieben,dieBeweiseexaktundseineLiteraturkenntnis ist hervorragend. “ • „Er ist didaktisch sehr geschickt. Er ist ein sehr ausdauernder und sehr schneller Arbeiter. “ • „EristneuenFragestellungengegenübersehraufgeschlossen,underarbeitet sich rasch in neue Fragestellungen ein.