From owner-theorynt@LISTSERV.NODAK.EDU Mon Jul 7 19:54:43 1997 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.5/8.8.5) with ESMTP id TAA29239 for ; Mon, 7 Jul 1997 19:54:43 -0700 (PDT) Received: from listserv.nodak.edu (listserv.NoDak.edu [134.129.111.8]) by CS.Stanford.EDU (8.8.6/8.8.6) with ESMTP id TAA04400; Mon, 7 Jul 1997 19:52:58 -0700 (PDT) Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.E7C648F0@listserv.nodak.edu>; Mon, 7 Jul 1997 21:51:21 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 2044760 for THEORYNT@LISTSERV.NODAK.EDU; Mon, 7 Jul 1997 21:51:18 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.E53DC950@listserv.nodak.edu>; Mon, 7 Jul 1997 21:51:16 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 2044740 for THEORY-A@LISTSERV.NODAK.EDU; Mon, 7 Jul 1997 21:51:16 -0500 Received: from usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.B3764190@listserv.nodak.edu>; Mon, 7 Jul 1997 21:49:53 -0500 Received: from pollux2.usc.edu (pollux2.usc.edu [128.125.253.192]) by usc.edu (8.8.4/8.7.2/usc) with ESMTP id TAA02707 for ; Mon, 7 Jul 1997 19:48:30 -0700 (PDT) Received: (from ierardi@localhost) by pollux2.usc.edu (8.8.4/8.8.4/usc) id TAA23554 for theory-a@listserv.nodak.edu; Mon, 7 Jul 1997 19:48:30 -0700 (PDT) X-Sun-Charset: US-ASCII Approved-By: Doug Ierardi Approved-By: Theory-A - TheoryNet World-Wide Events Message-ID: <9706300824.AA19692@wigry.mimuw.edu.pl> Date: Mon, 7 Jul 1997 19:48:30 PDT Reply-To: Theory-A - TheoryNet World-Wide Events , "Bogdan S. Chlebus" Sender: TheoryNet List From: "Bogdan S. Chlebus" Subject: FCT'97: call for participation Comments: To: THEORY-A@LISTSERV.NODAK.EDU To: THEORYNT@LISTSERV.NODAK.EDU Status: O X-Mozilla-Status: 0001 Content-Length: 10837 C A L L F O R P A R T I C I P A T I O N FCT'97 11-th International Symposium on Fundamentals of Computation Theory 1-3 September 1997, Krakow, Poland This document contains a full program, complete local information and a registration form. Full conference and registration information is also available at http://zaa.mimuw.edu.pl/~fct ----------------------------------------------------------------- GENERAL INFORMATION: The symposia on Fundamentals of Computation Theory are held every two years, and are a forum to present original research in all areas of theoretical computer science. This symposium will have plenary lectures by 6 invited speakers and parallel sessions for presenting 34 technical contributions in the following subject areas: (1) algorithms and complexity; (2) formal and logical methods. All the presented papers will be published in the conference proceedings in the Lecture Notes in Computer Science series of Springer Verlag. Krakow is a medieval town in southern Poland. It has good airplane and railway connections. The conference facilities, including hotel and restaurant, will be located in Krakow-Przegorzaly, in a castle on a cliff of the Vistula river, relatively close to downtown but isolated from the city. - Invited Speakers - Georg Gottlob (Technical University of Vienna) Ming Li (University of Waterloo and City University of Hong Kong) Antoni Mazurkiewicz (Polish Academy of Sciences) Daniel Spielman (Massachusetts Institute of Technology) Eli Upfal (Weizmann Institute and IBM Almaden) Martin Wirsing (University of Munich) - Program Committee - B. Chlebus (Warszawa, co-chair), G. Ciobanu (Iassy), L. Czaja (Warszawa, co-chair), Z. Esik (Szeged), J. Gruska (Bratislava), Jifeng He (Oxford), M. Karpinski (Bonn and Berkeley), M. Kutylowski (Paderborn and Wroclaw), A. Lingas (Lund), A. Maggiolo-Schettini (Pisa), V. Nepomniaschy (Novosibirsk), C. Papadimitriou (Berkeley), J. Rolim (Geneva), A. Salwicki (Pau), P. Spirakis (Patras), P. Starke (Berlin), R. Valk (Hamburg), J. van Leeuwen (Utrecht), K. Wagner (Wuerzburg), M. Zaionc (Krakow). ----------------------------------------------------------------- PROGRAM: SUNDAY, August 31 Afternoon and evening: conference registration Evening: welcome party MONDAY, September 1 Early morning: conference registration 8:50 - 9:00 Welcome address 9:00 - 11:00 Invited Lectures: "The Complexity of Error-Correcting Codes" Daniel Spielman "Proof Systems for Structured Algebraic Specifications: An Overview" Martin Wirsing 11:00 - 11:30 Coffe Break 11:30 - 12:45 Parallel Session A: Parallel Algorithms "k-k Sorting on the Multi-Mesh" A. Avermiddig, M. Kunde, A. Osterloh "Efficient Parallel Computing with Memory Faults" L. Gasieniec, P. Indyk "Towards Optimal Locality in Mesh-Indexings" R. Niedermeier, K. Reinhardt, P. Sanders 11:30 - 12:45 Parallel Session B: Petri Nets "Refinement of Coloured Petri Nets" E. Best, T. Thielke "Stratified Petri Nets" E. Badouel, P. Darondeau "On Occurrence Net Semantics for Petri Nets with Contacts" I.A. Lomazova 12:45 - 14:45 Lunch 14:45 - 16:00 Parallel Session A: Distributed Algorithms "Trade-off Results for Connection Management" M. Mavronicolas, N. Papadakis "Distributed Acyclic Orientation of Anonymous Asynchronous Networks" A. Calabrese "A Note on Broadcasting with Linearly Bounded Transmission Faults in Constant Degree Networks" K. Ciebiera, A. Malinowski 14:45 - 16:00 Parallel Session B: Word Problems and Rewriting Systems "The Subword Complexity of Fixed Points of Binary Uniform Morphisms" A.E. Frid "FDT Is Undecidable for Finitely Presented Monoids with Solvable Word Problems" F. Otto, A. Sattler-Klein "Unique Normal Forms for Nonlinear Term Rewriting Systems: Root Overlaps" R. M. Verma 16:00 - 16:30 Coffe Break 16:30 - 17:20 Parallel Session A: Algebra and Learning "The Complexity of the Coverability, the Containment and the Equivalence Problems for Commutative Semigroups" U. Koppenhagen, E.W. Mayr "The Complexity of Universal Text-Learners" F.C. Stephan, S.A. Terwijn 16:30 - 17:20 Parallel Session B: Logics and Complexity Classes "Logics Which Capture Complexity Classes over the Reals" F. Cucker, K. Meer "On an optimal Quantified Propositional Proof System and a Complete Language for NP \cap co-NP" Z. Sadowski TUESDAY, September 2 9:00 - 11:00 Invited Lectures: "Locally Computable Enumerations" Antoni Mazurkiewicz "Average-case analysis via incompressibility" Ming Li 11:00 - 11:30 Coffe Break 11:30 - 12:45 Parallel Session A: Automata and Algorithms "On the Average Complexity of the Membership Problem for a Generalized Dyck Language" M. E. Nebel "Pattern-Matching Problems for 2-Dimensional Images Described by Finite Automata" J. Karhumaki, W. Plandowski, W. Rytter "Cellular Automata Universality Revisited" B. Martin 11:30 - 12:45 Parallel Session B: Concurrency "Generalized Rational Relations and their Logical Definability" C. Choffrut, L. Guerra "Behavioural Characterisations of Partial Order Logics" I. Virbitskaite, A. Votintseva "Bounded Concurrency" D.P. Gruska 12:45 - 14:45 Lunch Later in the afternoon and evening: excursion and conference dinner WEDNESDAY, September 3 9:00 - 11:00 Invited Lectures: "Stochastic Analysis of Dynamic Processes" Eli Upfal "The Complexity Class \Theta^{p}_{2}: Recent Results and Applications in AI and Modal Logic" Georg Gottlob 11:00 - 11:30 Coffe Break 11:30 - 12:45 Parallel Session A: Computational Geometry "A Linear Time Heuristic for Minimum Rectangle Coverings" C. Levcopoulos, J. Gudmundsson "Concerning the Time Bounds of Existing Shortest Watchman Route Algorithms" M. Hammar, B. J. Nilsson "Lower Bounds in On-line Geometric Searching" S. Schuierer 11:30 - 12:45 Parallel Session B: Finite Automata "Synchronization of 1-way connected processors" S. La Torre, M. Napoli, M. Parente "From Finite Automata toward Hybrid Systems" A. Rabinovich, B.A. Trakhtenbrot "The Equivalence of Pebbles and Sensing Heads for Finite Automata" H. Petersen 12:45 - 14:45 Lunch 14:45 - 16:00 Parallel Session A: Structural Complexity "On the Hierarchy of Nondeterministic Branching k-Programs" E.A. Okol'nishnikova "Query Order in the Polynomial Hierarchy" E. Hemaspaandra, L. A. Hemaspaandra, H. Hempel "Polynomial Time Machines Equipped with Word Problems over Algebraic Structures as their Acceptance Criteria" U. Hertrampf 14:45 - 16:00 Parallel Session B: Formal Languages "Criteria to Disprove Context-Freeness of Collage Languages" F. Drewes, H.-J. Kreowski, D. Lapoire "Contextual Grammars with Distributed Catenation and Shuffle" M. Kudlek, S. Marcus, A. Mateescu "A Two-Dimensional Hierarchy for Attributed Tree Transducers" A. Kuhnemann End of FCT'97 ------------------------------------------------------------- CONFERENCE FEE: The REGULAR conference fee covers welcome party, breakfasts, lunches, refreshments during breaks, conference dinner, excursion, and a copy of the proceedings. The STUDENT conference fee covers welcome party, breakfasts, lunches, and refreshments during breaks. The ACCOMPANYING PERSON conference fee covers welcome party, breakfasts, lunches, conference dinner, and excursion. Conference fee amounts to: EARLY (by the end of July): regular: 400 DEM 710 PLN student: 200 DEM 370 PLN accompanying person: 270 DEM 480 PLN LATE (after July 31): regular: 430 DEM 750 PLN student: 230 DEM 400 PLN accompanying person: 300 DEM 500 PLN ----------------------------------------------------------- HOTEL: The participants will be accommodated in the hotel of the Polonia Institute at the conference site. All the rooms are double, with shower. The prices of hotel rooms below are per one day: single occupancy: 37 DEM 65 PLN double occupancy per one person: 23 DEM 40 PLN ----------------------------------------------------------- PAYMENT: The conference fee and hotel charges need to be transferred to the bank account of the Warsaw University. The account number depends on whether you pay in German marks (DEM) or in Polish zlotys (PLN). BANK: Bank Gdanski S.A. IV O Warszawa ACCOUNT NUMBER FOR PLN: 10401019-837 ACCOUNT NUMBER FOR DEM: 10401019-837-151-9795 ADDITIONAL SPECIFICATION: Wydzial MIM: FCT Please do not forget to: - make your payment after the confirmation of hotel reservation, when the hotel charge is known; - make sure that the payment carries your name and is free of bank charges; - bring a written confirmation of the transfer of funds from your bank. It will be possible to pay in cash (in Polish zlotys) at the conference desk. ----------------------------------------------------------- GETTING THERE: There are numerous convenient plane and train connections to Krakow. More on this can be found on the web page at the link to the conference venue. The address of the conference facilities: Instytut Polonijny Jodlowa 13 30-252 Krakow-Przegorzaly Poland Phone: +(48 12) 21-98-55, 21-97-81, 21-96-32, 22-49-94 ext. 364 Fax: +(48 12) 21-98-77 E-mail: office@apus.filg.uj.edu.pl The participants are expected to arrive on Sunday, August 31. The registration office will be opened on Sunday, August 31, in the afternoon and evening, and on Monday, September 1, in the morning. ----------------------------------------------------------- REGISTRATION: Send the filled in registration form to: fct97@ii.uj.edu.pl The form includes your preference concerning single/double occupancy of a hotel room. Single occupancy may be available for a limited number of participants. An acknowledgement of the receipt of the registration form will include a confirmation of a hotel reservation, and will clarify the issue of occupancy of your room. ----------------------------------------------------------- QUESTIONS: Any questions about local arrangements could be sent to: fct97@ii.uj.edu.pl ----------------------------------------------------------- FCT'97 REGISTRATION FORM First Name: Last Name: ___Male___Female Affiliation: Address: Telephone: Fax: E-mail: Arrival: Departure: Number of nights at the hotel: Hotel room:___single occupancy___double occupancy Accompanying person: I want to share a room with: Payment:___bank transfer___cash at the conference desk Meals:___regular ___vegetarian Special needs, if any: