Lecture Notes in Computer Science
2 primary works
Book 454
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.
Book 3404
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.
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.