From - Tue Jan 13 02:58:17 1998 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.7/8.8.7) with ESMTP id BAA18357 for ; Tue, 16 Dec 1997 01:52:02 -0800 (PST) Received: from listserv.nodak.edu (listserv.NoDak.edu [134.129.111.8]) by CS.Stanford.EDU (8.8.8/8.8.8) with ESMTP id BAA28606; Tue, 16 Dec 1997 01:52:52 -0800 (PST) Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.7E68EA70@listserv.nodak.edu>; Tue, 16 Dec 1997 3:48:39 -0600 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 531813 for THEORYNT@LISTSERV.NODAK.EDU; Tue, 16 Dec 1997 03:48:35 -0600 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.7B868760@listserv.nodak.edu>; Tue, 16 Dec 1997 3:48:34 -0600 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 531801 for THEORY-A@LISTSERV.NODAK.EDU; Tue, 16 Dec 1997 03:48:33 -0600 Received: from pollux.usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.7AA8D190@listserv.nodak.edu>; Tue, 16 Dec 1997 3:48:32 -0600 Received: (from ierardi@localhost) by pollux.usc.edu (8.8.8/8.8.8/usc) id BAA00158 for theory-a@listserv.nodak.edu; Tue, 16 Dec 1997 01:48:29 -0800 (PST) X-Emacs: Local Variables: X-Emacs: 8-bit-TeX-convention: TeX X-Emacs: mode: 8-bit X-Emacs: End: Approved-By: Doug Ierardi Approved-By: Theory-A - TheoryNet World-Wide Events Message-ID: <199712102040.VAA08991@litp.liafa.jussieu.fr> Date: Tue, 16 Dec 1997 01:48:29 PST Reply-To: Theory-A - TheoryNet World-Wide Events , Michel MORVAN Sender: TheoryNet List From: Michel MORVAN Subject: STACS 98 program and registration Comments: To: THEORY-A@LISTSERV.NODAK.EDU To: THEORYNT@LISTSERV.NODAK.EDU Status: O X-Status: SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE STACS'98 Paris (France) February 25-27, 1998 1st ANNOUNCEMENT ****************************************************************************** This mail contains the following informations in ASCII format concerning the 15-th Symposium on Theoretical Aspects of Computer Science (STACS'98) : 1) Programme of the conference 2) Registration form 3) Practical informations (location, transportation, hotels, etc) 4) Sponsors ****************************************************************************** 1 - Programme of the Conference ****************************************************************************** Wednesday, February 25, 1998 Plenary session I. Chair: M. Morvan 09:30 - 10:30 : Opening talk by Richard Karp 10:30 - 11:00 : Coffee break ------------------------ Parallel session I.1: Algorithms and Data Structures I. Chair: G. Italiano 11:00 - 11:30 Authors: M. Janssen, D. Krizanc, L. Narayanan and S. Shende. Title: Distributed Online Frequency Assignment in Cellular Networks 11:30 - 12:00 Authors: M. Thorup. Title: Floats, Integers, and Single Source Shortest Paths 12:00 - 12:30 Authors: M. Habib, C. Paul and L. Viennot. Title: A Synthesis on Partition Refinement: a useful Routine for Strings, Graphs, Boolean Matrices and Automata ------------------------ Parallel session I.2: Logic I. Chair: T. Ehrhard 11:00 - 11:30 Authors: J. C. Bradfield. Title: Simplifying the modal mu-calculus alternation hierarchy 11:30 - 12:00 Authors: T. Eiter, T. Ibaraki and K. Makino. Title: On Disguised Double Horn Functions and Extensions 12:00 - 12:30 Authors: S. Demri and P. Schnoebelen. Title: The Complexity of Propositional Linear Temporal Logics in Simples Cases ------------------------ 12:30 - 14:00 : Lunch ------------------------ Parallel session II.1: Complexity I. Chair: J. Rolim 14:00 - 14:30 Authors: D. A. M. Barrington, C.-J Lu, P. B. Miltersen and S. Skyum. Title: Searching constant width mazes captures the AC^0 hierarchy 14:30 - 15:00 Authors: L. Fortnow and S. Laplante. Title: Nearly Optimal Language Compression using Extractors 15:00 - 15:30 Authors: J. H. Spencer and K. St. John. Title: Limit Probabilities for Random Sparse Bit Strings 15:30 - 16:00 Authors: M. Sauerhoff. Title: Lower Bounds for Randomized Read-k-Times Branching Programs ------------------------ Parallel session II.2: Automata and Formal Languages I. Chair: D. Krob 14:00 - 14:30 Authors: J. Mazoyer and I. Rapaport. Title: Inducing an Order on Cellular Automata by a Grouping Operation 14:30 - 15:00 Authors: G. Manzini and L. Margara. Title: Attractors of D-dimensionalLinear Cellular Automata 15:00 - 15:30 Authors: C. Mereghetti and G. Pighizzini. Title: Optimal Simulations Between Unary Automata 15:30 - 16:00 Authors: A. Mateescu Title: Shuffle of $\omega$-Words: Algebraic Aspects ------------------------ 16:00 - 16:30 : Coffee break ------------------------ Parallel session III.1: Complexity II. Chair: U. Hertrampf 16:30 - 17:00 Authors: H. Buhrman, D. van Melkebeek, K. Regan, R. Sivakumar and M. Strauss. Title: A generalization of Resource-Bounded Measure, With an Application 17:00 - 17:30 Authors: V. Arvind, R. Beigel and A. Lozano. Title: The Complexity of Modular Graph Automorphism 17:30 - 18:00 Authors: L. Libkin and L. Wong. Title: Unary Quantifiers, Transitive Closure, and Relations of Large Degree 18:00 - 18:30 Authors: P. Buergisser. Title: On the Structure of Valiant's Complexity Classes ------------------------ Parallel session III.2: Algorithms and Data Structures II. Chair: C. Meinel 16:30 - 17:00 Authors: D. Sieling. Title: On the Existence of Polynomial Time Approximation Schemes for OBDD-Minimization 17:00 - 17:30 Authors: J. Feigenbaum, S. Kannan and M. Y. Vardi. and Viswanathan, Mahesh Title: Complexity of Problems on Graphs Represented as OBDDs 17:30 - 18:00 Authors: J. Behrens and S. Waack. Title: Equivalence Test and Ordering Transformation for Parity--OBDDs of Different Variable Ordering 18:00 - 18:30 Authors: C. Gr{\"o}pl and H. J. Pr{\"o}mel. and Srivastav, Anand Title: Size and Structure of Random Ordered Binary Decision Diagrams -------------------------- 19:00 : Reception ------------------------------------------------------------------ Thursday, Feburary 26, 1998 Plenary session II. Chair: M. Morvan 09:00 - 10:00 : Invited talk by Serge Vaudenay 10:00 - 10:30 : Coffee break ------------------------ Parallel session IV.1: Algorithms and Data Structures III. Chair: M. Henzinger 10:30 - 11:00 Authors: C. Bazgan, M. Santha and Z. Tuza. Title: On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs 11:00 - 11:30 Authors: K. Jansen. Title: The mutual exclusion scheduling problem for permutation and comparability graphs 11:30 - 12:00 Authors: N. H. Bshouty and L. J. Burroughs. Title: Massaging a Linear Programming Solution to Give a 2-Approximation For a Generalization of the Vertex Cover Problem 12:00 - 12:30 Authors: K. S. Larsen. Title: Partially Persistent Search Trees with Transcript Operations ------------------------ Parallel session IV.2: Automata and Formal Languages II. Chair: J. Berstel 10:30 - 11:00 Authors: D. Niwinski and I. Walukiewicz. Title: Relating hierarchies of word and tree automata 11:00 - 11:30 Authors: H. Straubing Title: Languages Defined with Modular Counting Quantifiers (extended abstract) 11:30 - 12:00 Authors: M. Jantzen. Title: On twist-closed trios 12:00 - 12:30 Authors: T. Safer. Title: Radix Representations of Algebraic Number Field and Finite Automata ------------------------ 12:30 - 14:00 : Lunch ------------------------ 14:00 : Guided visit of the Orsay Museum ------------------------------------------------------------------ Friday, February 27, 1998 Plenary session III. Chair: C. Meinel 09:00 - 10:00 : Invited talk by Torben Hagerup 10:00 - 10:30 : Coffee break ------------------------ Parallel session V.1: Algorithms and Data Structures IV. Chair: F. Otto 10:30 - 11:00 Authors: M. Diallo, A. Ferreira and A. Rau-Chaplin. Title: Communication-Efficient Deterministic Parallel Algorithms for Planar Point Location and 2d Voronoi Diagram 11:00 - 11:30 Authors: C. Rueb. Title: On Batcher's Merge Sorts as Parallel Sorting Algorithms 11:30 - 12:00 Authors: J. Gustedt. Title: Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel 12:00 - 12:30 Authors: A. Dessmark, A. Lingas and H. Olsson. and Yamamoto, Hiroaki Title: Optimal broadcasting in almost trees and partial k-trees ------------------------ Parallel session V.2: Logic II. Chair: E. Graedel 10:30 - 11:00 Authors: T. Schwentick and K. Barthelmann. Title: Local Normal Forms for First-Order Logic with Applications to Games and Automata 11:00 - 11:30 Authors: Z. Esik. Title: Axiomatizing the Equational Theory of Regular Tree Languages, Extended Abstract 11:30 - 12:00 Authors: A. Monti and A. Peron. Title: A Logical Characterization of Systolic Languages 12:00 - 12:30 Authors: J. Messner and J. Tor\'an. Title: Optimal Proof Systems for Propositional Logic and Complete Sets ------------------------ 12:30 - 14:00 : Lunch (Wine and cheese) ------------------------ Parallel session VI.1: Complexity III. Chair: J. Lutz 14:00 - 14:30 Authors: M. Serna, L. Trevisan and F. Xhafa. Title: The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming 14:30 - 15:00 Authors: S. Ivanov and M. de Rougemont. Title: Interactive Protocols on the reals 15:00 - 15:30 Authors: G. Di Crescenzo, K. Sakurai and M. Yung. Title: Result-Indistinguishable Zero-Knowledge Proofs: increased power and constant-round protocols 15:30 - 16:00 Authors: S. De Agostino and R. Silvestri. Title: Bounded Size Dictionary Compression: SC^k-Completeness and NC Algorithms ------------------------ Parallel session VI.2: Automata and Formal Languages III. Chair: J. Karhumaki 14:00 - 14:30 Authors: R. Meyer and A. Petit. Title: Expressive Completeness of LTrL on Finite Traces: an Algebraic Proof 14:30 - 15:00 Authors: A. E. Frid. Title: On the Uniform DOL Words 15:00 - 15:30 Authors: C. Allauzen. Title: PCP(3) is decidable for marked morphisms 15:30 - 16:00 Authors: K. Lodaya and P. Weil. Title: Series-parallel posets: algebra, automata and languages ------------------------ 16:00 - 16:30 : Coffee break ------------------------ Parallel session VII.1: Algorithms and Data Structures V. Chair: J.-M. Fedou 16:30 - 17:00 Authors: R. Kemp. Title: On the expected number of nodes at level k in 0-balanced trees 17:00 - 17:30 Authors: M. C. Golumbic and H. Kaplan. Title: Cell Flipping in Permutation Diagrams 17:30 - 18:00 Authors: M. Dorkenoo and M.-C. Eglin-Leclerc and E. R\'emila. Title: Construction of non-intersecting colored flows through a planar cellular figure ------------------------ Parallel session VII.2: Complexity IV. Chair: A. Steger 16:30 - 17:00 Authors: C. S. Calude, P. H. Hertling, B. Khoussainov and Y. Wang. Title: Recursively Enumerable Reals and Chaitin Omega Numbers 17:00 - 17:30 Authors: S. Kosub, H. Schmitz and H. Vollmer. Title: Uniformly Defining Complexity Classes of Functions 17:30 - 18:00 Authors: D. Lapoire. Title: Recognizability equals Monadic Second-Order definability, for sets of graphs of bounded tree-width -------------------------- 19:00 : Conference dinner ****************************************************************************** 2 - Registration Form ****************************************************************************** Please send back this registration form with the required informations to : Nicole Godard - STACS'98 - University Paris 7 - LIAFA - 2, place Jussieu - 75251 Paris Cedex 05 ------------------------------------------------------------------------------ Family Name: Name: Title: Affiliation: Postal Address: E-mail: Telephone: Fax: Date of arrival: Date of departure: Member of GI (circle the good information): Yes No Student (circle the good information): Yes No N.B. GI members or students are required to confirm their status with some official paper Registration Fees (in french francs (FF)) -------------------------------------------------------- | | | | Before January 26, 1998 | After January 26, 1998 | | | | |-------------------------|------------------------------------------------------- | | | | | Academic Normal Price | 1650 FF | 2050 FF | | | | | |-------------------------|------------------------------------------------------- | | | | | GI Member | 1450 FF | 1850 FF | | | | | |-------------------------|------------------------------------------------------- | | | | | Student | 950 FF | 1150 FF | | | | | |-------------------------|------------------------------------------------------- | | | | | Industry Member | 4000 FF | 4500 FF | | | | | |-------------------------|------------------------------------------------------- The conference banquet and the proceedings volume of LNCS is included in the fees. The price of the banquet for non participants is fixed at 350 FF. Paiement: --------- Registration Fees: FF Extra places for the banquet: 350 FF * = FF Total: FF Paiement should be made only in FRENCH FRANCS at the order of "Maison de l'Informatique et des Mathematiques Discretes (MIMD)" using one of the following modes of paiement: 1) by bank transfer at the following bank account of the MIMD: Name of bank: BRED Address: BRED - Agence de Rouen Saint-Marc - Rue de Martainville 76000 Rouen - France Bank Code: 10107 Agency Code: 00370 Bank account: 00131 70 9620 (92) Owner of the bank account: Maison de l'Informatique et des Mathematiques Discretes (MIMD) Add to your the following references: MIMD/STACS98 and your name N.B. If you use this mode of paiement, all banking transfer costs should be at your charge. 2) by credit card: indicate then the credit card used and send us back this form signed and with the following informations: (circle the good information) Visa Master Card Eurocard Credit Card Number: Date of Expiration: Signature: 3) by check written in frech money at the order of MIMD. ****************************************************************************** 3 - Practical Informations ****************************************************************************** Location: --------- The conference will take place in the old site of the Ecole Polytechnique in the very center of the Quartier Latin in Paris. The conference site is precisely located at the following address: Ministere de l'Education Nationale, de la Recherche et de la Technologie Carre des Sciences 1, rue Descartes 75005 Paris Transportation: --------------- Reaching Paris should normally not be a problem! For going to the conference site, public transportations are clearly the more convenient. The nearest underground (Metro) station is "Cardinal Lemoine". A five minutes walk is then required to reach the conference site. More transportation informations can be found on the web at - http://www.liafa.jussieu.fr/~stacs98 (STACS'98 servor) - http://metro.jussieu.fr:10001/bin/select/english/france/paris (how to compute an underground route in paris) Conference events: ------------------ A reception will take place on Wednesday at 19:00 at the very top (24th floor) of Jussieu tower (one of the most beautiful view on Paris by night). On Thursday afternoon, a guided tour of the Orsay Museum will give a (small) overview of the local cultural life. A "vin et fromage" (wine and cheese) will be organised in place of Friday's lunch followed finally by the conference banquet on Friday evening. Hotels: ------- We will not manage hotel reservations. The participants are therefore required to book individually their hotels. A list of hotels where special prices were negociated for STACS'98 will be sent in the second announcement and will be soon available on the web site of the conference (see below). We recommand to make reservations as soon as possible. For more information: --------------------- STACS'98 Web site: http://www.liafa.jussieu.fr/~stacs98 STACS'98 e-mail address: stacs98@liafa.jussieu.fr ****************************************************************************** 4 - Sponsors ****************************************************************************** STACS'98 is sponsored by European Community, Ministere des Affaires Etrangeres (MAE), Laboratoire d'Informatique Algorithmique - Fondements et Applications (LIAFA) et Centre National de la Recherche Scientifique (CNRS). STACS'98 is coorganized by GI, LIAFA and MIMD.