For up-to-date information, travel the WWW to URL http://hpmayr1.informatik.tu-muenchen.de/stacs95 or use anonymous ftp to ftp.informatik.tu-muenchen.de, path /local/lehrstuhl/mayr/stacs95 ssss ttttt a ccc ssss ' 999 55555 s t a a c s 9 9 5 sss t a a c sss 9999 5555 s t aaaaa c s 9 5 ssss t a a ccc ssss 999 5555 =========================================== The Symposium on Theoretical Aspects of Computer Science is held annually, alternating between Germany and France. STACS is organized jointly by the Special Interest Group for Theoretical Computer Science of Gesellschaft fuer Informatik (GI) and the Special Interest Group for Applied Mathematics of afcet. STACS '95, the 12th in this series, will be held in Munich, March 2-4, 1995. The symposium will feature invited talks and the presentation of original research papers. The proceedings will be published by Springer in Lecture Notes in Computer Science. 180 papers have been submitted from all over the world, e.g. United States, Australia, Japan, Russia and nearly every European country. They discuss new results from many areas of computer science, including algorithms and data structures, automata and formal languages, computational complexity, computational geometry, cryptography, learning theory, logic in computer science, parallel algorithms, semantics of programming languages, theory of data bases, theory of parallel and distributed computation, and VLSI structures. 53 papers have been selected for presentation in this symposium, giving you an overview on outstanding research results in computer science. We encourage you to participate in what promises to be an exciting and important event. PROGRAMM ======== Thursday, March 2 ================= 8.25 Welcome 8.30 Invited Talk: On the Synthesis of Nonterminating Reactive Programs, W. Thomas Session 1A: Complexity Theory I 9.30 Finding the Maximum with Linear Error Probabilities: A Sequential Analysis Approach, G. Louchard 9.55 Completeness and Weak Completeness Under Polynomial-Size Circuits, David W. Juedes, Jack H. Lutz Session 1B: Cryptography 9.30 Communication Complexity of Key Agreement on Small Ranges, Jin-Yi Cai, Richard J. Lipton, Luc Longpre, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar 9.55 Pseudorandom Generators and the Frequency of Simplicity, Yenjo Han, Lane A. Hemaspaandra 10.20 Coffee Break Session 2A: Complexity Theory II 10.50 Classes of Bounded Counting Type and their Inclusion Relations, Ulrich Hertrampf 11.15 Lower Bounds for Depth-Three Circuits With Equals and Mod-Gates, Frederic Green 11.40 On Realizing Iterated Multiplication by Small Depth Threshold Circuits, Matthias Krause 12.05 A Random NP-Complete Problem for Inversion of 2D Cellular Automata, Bruno Durand Session 2B: Automata Theory I 10.50 On the Subword Equivalence Problem for Infinite Words, Isabelle Fagnot 11.15 On the Separators of an Infinite Word Generated by a Morphism, Emmanuelle Garel 11.40 Systolic Tree $\omega$-Languages, Angelo Monti, Adriano Peron 12.05 Structural Complexity of $\omega$-Automata, Sriram C. Krishnan, Anuj Puri, R.K. Brayton, P. Varaiya 12.30 Lunch Session 3A: Algorithms 14.00 Algorithms Explained by Symmetries, Torsten Minkwitz 14.25 Generalized Scans and Tri-Diagonal Systems, Paul F. Fischer, Franco P. Preparata, John E. Savage 14.50 Two-Dimensional Pattern Matching in Linear Time and Small Space, Maxime Crochemore, Leszek Gasieniec, Wojciech Plandowski, Wojciech Rytter 15.15 On-line and Dynamic Algorithms for Shortest Path Problems, Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis Session 3B: Logic 14.00 On Compact Representations of Propositional Circumscription, Marco Cadoli, Francesco M. Donini, Marco Schaerf 14.25 A Set-Theoretic Translation Method for (Poly)modal Logics, Giovanna D'Agostino, Angelo Montanari, Alberto Policriti 14.50 On the Synthesis of Discrete Controllers for Timed Systems, Oded Maler, A. Pnueli, J. Sifakis 15.15 A Fully Abstract Semantics for Causality in the $\pi$-Calculus, Michele Boreale, Davide Sangiorgi 15.40 Coffee Break Session 4A: Theory of Parallel Computing I 16.10 On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks, J. Hromkovic, K. Lorys, P. Kanarek, R. Klasing, W. Unger, H. Wagener 16.35 Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations, Friedhelm Meyer auf der Heide, Christian Scheideler, Volker Stemann 17.00 Interval Routing Schemes, Michele Flammini, Giorgio Gambosi, Sandro Salomone 17.25 A Packet Routing Protocol for Arbitrary Networks, Friedhelm Meyer auf der Heide, Berthold Vocking Session 4B: Automata Theory II 16.10 A Family of Tag Systems for Paperfolding Sequences, Christiane Bercoff 16.35 Growing Context-Sensitive Languages and Church-Rosser Languages, Gerhard Buntrock, Friedrich Otto 17.00 Deterministic Generalized Automata, Dora Giammarresi, Rosa Montalbano 17.25 Optimal Simulation of Automata by Neural Nets, Piotr Indyk Friday, March 3 =============== 8.30 Invited Talk: Concurrent Process Equivalences: Some Decision Problems, A. R. Meyer Session 5A: Communication Theory 9.30 Optimal Lower Bounds on the Multiparty Communication Complexity, Pavol Duris, Jose Rolim 9.55 Simultaneous Messages vs. Communication, Laszlo Babai, Peter Kimmel, Satyanarayana V. Lokam Session 5B: Automata Theory III 9.30 Coding and Strong Coding in Trace Monoids, Veronique Bruyere, Clelia De Felice 9.55 On Codings of Traces, Volker Diekert, Anca Muscholl, Klaus Reinhardt 10.20 Coffee Break Session 6A: Graph Theory, Data Bases 10.50 Finding Largest Common Embeddable Subtrees, Arvind Gupta, Naomi Nishimura 11.15 The $\chi_t$-Coloring Problem, Damon Kaller, Arvind Gupta, Tom Shermer 11.40 Expander Properties in Random Regular Graphs with Edge Faults, S.E. Nikoletsas, P.G. Spirakis 12.05 Dynamic Analysis of the Sizes of Relations, Daniele Gardy, Guy Louchard Session 6B: Automata Theory IV 10.50 On Slender Context-Free Languages, Danny Raz 11.15 Partial Derivatives of Regular Expressions and Finite Automata Constructions, Valentin Antimirov 11.40 Dependence Orders for Computations of Concurrent Automata, Felipe Bracho, Manfred Droste, Dietrich Kuske 12.05 On the Undecidability of Deadlock Detection in Families of Nets, Anne-Cecile Fabret, Antoine Petit 12.30 Lunch Session 7A: Thoery of Parallel Computing II 14.00 On the Average Running Time of Odd-Even Merge Sort, Christine Rub 14.25 Optimal Average Case Sorting on Arrays, Manfred Kunde, Rolf Niedermeier, Peter Rossmanith, Klaus Reinhardt Session 7B: Complexity Theory III 14.00 Normal Numbers and Sources for BPP, Martin Strauss 14.25 Lower Bounds on Learning Decision Lists and Trees, Thomas Hancock, Tao Jiang, Ming Li, John Tromp 15.45 Social Event (to be announced) 19.00 Conference Dinner Saturday, March 4 ================= Session 8A: Computational Geometry 8.45 Line Segmentation of Digital Curves in Parallel, Peter Damaschke 9.10 Computability of Convex Sets, Martin Kummer, Marcus Schafer 9.35 Enumerating Extreme Points in Higher Dimensions, Th. Ottmann, S. Schuierer, S. Soundaralakshmi 10.00 The Number of Views of Piecewise-Smooth Algebraic Objects, Sylvain Petitjean Session 8B: Complexity Theory IV 8.45 On the Structure of log-Space Probabilistic Complexity Classes, Ioan I. Macarie 9.10 Resource-Bounded Instance Complexity, Lance Fortnow, Martin Kummer 9.35 On the Sparse Set Conjecture for Sets with Low Density, Harry Buhrman, Montserrat Hermo 10.00 Beyond $P^{NP}=NEXP$, Stephen Fenner, Lance Fortnow 10.25 Coffee Break Session 9: Complexity Theory V 10.55 Malign Distributions for Average Case Circuit Complexity, Andreas Jakoby, Rudiger Reischuk, Christian Schindelhauer 11.20 Invited Talk Statistical Properties in Genes, their Simulation by Stochastic Automata: An Application to the Genetic Code, D. Arques REGISTRATION ============ Please fill in the registration form (type or use block letters) and send it together with a euro-check or international money order made out in German marks and payable to Ernst W. Mayr/STACS '95 to: Ernst W. Mayr Institut fuer Informatik Technische Universitaet Muenchen D-80290 Muenchen Germany The non-student registration fee includes the Wednesday night reception, the Friday excursion and conference dinner, coffee breaks (Thursday, Friday and Saturday) and lunches (Thursday and Friday), and a copy of the proceedings. The student fee includes the reception, coffee breaks and lunches. Students must include a note from their department or supervisor verifying student status. To qualify for the early registration fee, your registration application must be received by Friday, December 30. Full payment in DM must accompany registration. Make sure that ALL bank charges are included. +-------------------+-----------------+-----------------+ | Table of fees | before Dec 30 | after Dec 30 | +-------------------+-----------------+-----------------+ | AFCET-GI member | DM 290,-- | DM 390,-- | | Non-member | DM 340,-- | DM 440,-- | | Student | DM 130,-- | DM 230,-- | +-------------------+-----------------+-----------------+ You also have the possibility to transfer the fee directly to Postbank Muenchen (BLZ 700 100 80), Account Ernst W. Mayr, keyword STACS '95, Acct. No. 5720 66-805. ACCOMMODATION ============= Blocks of rooms have been reserved at various hotels at favorable rates, but reservations must be received by the hotel by DECEMBER 30. These hotels are located near the main railway station, a 15 minute walk away from the Technische Universitaet Muenchen. The rooms are divided into two categories. Rates per room and per night, including breakfast and taxes: +--------------+-------------------+-------------------+ | | Single room: | Double room: | +--------------+-------------------+-------------------+ | Category 1: | DM 87,- | DM 130,- | +--------------+-------------------+-------------------+ | Category 2: | DM 118,- to 146,- | DM 150,- to 176,- | +--------------+-------------------+-------------------+ For reservation in category 1, please fill in the enclosed reservation form. Note that there are 50 single rooms and 40 double rooms available in category 1. The organizers will consider the reservations on a first-come-first-served basis. If no more rooms are available in category 1 you will automatically get a room in a hotel of category 2. For reservation in category 2, please contact yourself one of the hotels listed below. Please be sure to identify yourself as a STACS (at the Technische Universitaet Muenchen) attendee when making your reservation and at check-in. Hotels Category 2 1)Hotel Meier Schuetzenstrasse 12 D-80335 Muenchen, Germany Phone: +49-89-59 56 23, Fax: +49-89-55 38 29 Single room: DM 118,- Double room: DM 166,- 2)Best Western Hotel ALTANO Arnulfstrasse 12 D-80335 Muenchen, Germany Phone: +49-89-55 18 80, Fax: +49-89-59 84 91 Single room: DM 120,- Double room: DM 170,- 3)Hotel Europaeischer Hof Bayerstra{\ss}e 31 D-80335 M\"unchen, Germany Phone: +49-89-55 15 10, Fax: +49-89-55 15 12 22 +---------------+----------+----------+ | | Komfort | Superior | +---------------+----------+----------+ | Single room: | DM 125,- | DM 146,- | +---------------+----------+----------+ | Double room: | DM 150,- | DM 176,- | +---------------+----------+----------+ All rates are per room and per night, including breakfast and taxes. GENERAL INFORMATION =================== Location ======== Munich (1.3 mio. inhabitants) is the capital of Bavaria and is located about 50 km north of the Alps in Central Europe. Munich was founded in 1158 by duke Heinrich dem Loewen. All conference events, except for the banquet, will take place in the Robert Sauer-Buildings (Arcisstrasse 16 or Barerstrasse 23) at the Technische Universitaet Muenchen, which is located in the center of Munich. Climate ======= The weather at the beginning of March is usually cold and wet. Day heights vary from 5 to 10 degrees Celsius, night lows vary from 0 to -5 degrees Celsius. Rain or snow is likely. Transportation ============== The international airport Munich II is located about 40 km northeast of Munich. Munich airport is served by the S-Bahn, a fast urban railway. It runs every 20 minutes except from 1:15 to 3:55 at night. The trip to the city of Munich takes 40 minutes and costs roughly DM 13,-. The rates for a cab are approximately DM 100,-. The main railway station of Munich is located in the center, a 15 minute walk away from the Technische Universitaet Muenchen. The conference hotels are located near the main railway station. Registration ============ The registration desk will be open from 15:00 until 21:00 on Wednesday, March 1, and during the day on Thursday and Friday. Conference Events ================= A reception will be held on Wednesday from 17:00 until 20:00 at the Technische Universitaet Muenchen. Drinks and Brezn (a bavarian speciality) will be served. Details on the excursion and the banquet will be provided on site. For accompanying persons, please ask at the registration desk for additional tickets. Lunches will be served in the Mensa on Thursday and Friday. Proceedings =========== Additional copies of the proceedings will be sold during the conference at the registration desk. Points of Interest ================== The main sights are located in or near the Old Town of Munich. The heart of the Old Town is the Marienplatz with the Old and New Town Hall. Near the Marienplatz you will find the well-known Cathedral of Munich named Frauenkirche and, in the opposite direction, the Viktualienmarkt, a large food market. Another interesting sight is the Royal Residence located north of the New Town Hall. Located at east of the Old Town, the German Museum offers you one of the biggest collection of science and technology exhibits in the world. The Old and New Pinakothek at the northern border of the Old Town exhibit paintings from the 14th century on. Further away from the center you will find the Nymphenburg Palace and the Olympic Park, where the Olympic Games took place in 1972. Of course, this is only a small and very incomplete list of sights to be found in Munich. Also note that the stout season starts at the beginning of March. Several bavarian breweries offer their own stout in their numerous beer halls. But be careful, don't get drunk. Organizing Committee ==================== E. Bayer, V. Heun, U. Koppenhagen, K. Kuhnle, E.W. Mayr, A. Schmidt, H. Stadtherr, I. Wohlrab. Program Committee ================= M. Ben-Or, I. Castellani, J.-P. Delahaye, M. Dietzfelbinger, Z. Esik, H. Ganzinger, D. Krob, E.W. Mayr, P. Pudlak, C. Puech, A. Restivo, P. Schmitt, U. Schoning, J. Stern, M. Yung. Sponsoring ========== STACS'95 is sponsored by GI, afcet, BMW, Cray, DFG, EU, IBM, and Sun Microsystems. Further Information =================== Please contact: Ernst W. Mayr\\ Institut fuer Informatik Technische Universitaet Muenchen\\ D-80290 Muenchen Germany Phone: +49-89-2105-2680 FAX: +49-89-2105-5297 Email: stacs@informatik.tu-muenchen.de For up to date information see WWW at URL: http://hpmayr1.informatik.tu-muenchen.de/stacs95 REGISTRATION FORM FOR STACS '95 =============================== Please fill in (type or use block letters) and return this form with proof of payment to Ernst W. Mayr Institut fuer Informatik Technische Universitaet Muenchen D-80290 Muenchen Germany. To avoid the late fee, payment must be received by FRIDAY, DECEMBER 30. [ ] Mr [ ] Ms Acad. Title: _____________________________________ First Name: _______________________ Name: ____________________________ Institute: ___________________________________________________________ Address: _____________________________________________________________ _____________________________________________________________ Country: _____________________________________________________________ Phone: ____________________________ FAX: _____________________________ Email: _______________________________________________________________ AFCET-GI No.: ________________________________________________________ Dietary restrictions: Vegetarian: _____________ None: _____________ The fees are listed below, all prices are in DM: +-------------------+-----------------+-----------------+ | | before Dec 30 | after Dec 30 | +-------------------+-----------------+-----------------+ | AFCET-GI member | DM 290,-- | DM 390,-- | | Non-member | DM 340,-- | DM 440,-- | | Student | DM 130,-- | DM 230,-- | +-------------------+-----------------+-----------------+ Students must include a note from their department or supervisor verifying student status. Registration fee: DM: ___________ Additional excursion and conference dinner tickets (DM 100,-) No.: ___________ DM: ___________ Total amount: DM: ___________ [ ] Euro-check (in DM) or money order (in DM) is enclosed. [ ] The money has already been transferred to Postbank Muenchen (BLZ 700 100 80), Account Ernst W. Mayr, keyword STACS '95, Acct.~No.~5720~66-805. Make sure that ALL bank charges are included. Date: ____.____.199__ Signature: ___________________________________ HOTEL RESERVATION FORM FOR CATEGORY 1 ===================================== For hotel reservation ONLY in CATEGORY 1 fill in (type or use block letters) and return this form to Ernst W. Mayr Institut fuer Informatik Technische Universitaet Muenchen D-80290 Muenchen Germany. For reservation in category 2, please contact the desired hotel your- self. Reservations must be made by FRIDAY, DECEMBER 30. Reservations made after that will be accepted on a rate and space avalaibility. Note that the number of rooms is limited. If no more rooms are avail- able in category 1 you will automatically get a room in a hotel of category 2. [ ] Mr [ ] Ms First Name: __________________________________________________________ Name: ________________________________________________________________ Address: _____________________________________________________________ _____________________________________________________________ _____________________________________________________________ Country: _____________________________________________________________ Phone: ____________________________ FAX: _____________________________ Arrival Date: ____.____.1995 Departure Date: ____.____.1995 [ ] Single room (DM 87,-) [ ] Double room (DM 130,-) Sharing double with: _____________________________________________ Rates are per room and per night, including breakfast and taxes. Smoking preference upon availability: [ ] smoking [ ] non-smoking Date: ____.____.199__ Signature: ___________________________________