(Message inbox:26) Return-Path: Received: from THEORY.CS.CMU.EDU by missing.link.cs.cmu.edu id ab19635; 6 Aug 96 2:07 EDT Received: from listserv.NoDak.edu by THEORY.CS.CMU.EDU id ab17940; 6 Aug 96 2:01:29 EDT Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.8F720B80@listserv.nodak.edu>; Tue, 6 Aug 1996 0:59:46 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8b) with spool id 805106 for THEORYNT@LISTSERV.NODAK.EDU; Tue, 6 Aug 1996 00:59:34 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.850AEDB0@listserv.nodak.edu>; Tue, 6 Aug 1996 0:59:28 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8b) with spool id 805049 for THEORY-A@LISTSERV.NODAK.EDU; Tue, 6 Aug 1996 00:59:23 -0500 Received: from pollux.usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.75F22EB0@listserv.nodak.edu>; Tue, 6 Aug 1996 0:59:03 -0500 Received: (from ierardi@localhost) by pollux.usc.edu (8.7.2/8.7.2/usc) id WAA21988 for theory-a@listserv.nodak.edu; Mon, 5 Aug 1996 22:59:01 -0700 (PDT) Approved-By: Doug Ierardi Approved-By: Theory-A - TheoryNet World-Wide Events Message-ID: <199608011038.MAA03921@Wars.IPIPAN.WaW.PL> Date: Mon, 5 Aug 1996 22:59:00 PDT Reply-To: Theory-A - TheoryNet World-Wide Events , Wojciech Penczek Sender: TheoryNet List Comments: cc: penczek@Wars.IPIPAN.WaW.PL From: Wojciech Penczek Subject: MFCS'96: FINAL CALL FOR PARTICIPATION Comments: To: Multiple recipients of list THEORY-A To: Local Distribution [Sorry if you receive this message more than once. --wp] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ PROGRAMME AND FINAL CALL FOR PARTICIPATION The 21st International Symposium on Mathematical Foundations of Computer Science (MFCS'96) September 2 - 6, 1996 Cracow, Poland The series of MFCS symposia, organized alternately in the Czech Republic, Poland and Slovakia since 1972, has a long and well-established tradition. The MFCS symposia encourage high-quality research in all branches of theoretical computer science and provide an opportunity to bring together specialists working in the area. Principal topics of interest include (but are not limited to): algorithms and data structures, automata and formal languages, complexity and computability, concurrency theory, data bases and knowledge-based systems, declarative programming, formal specifications and programd evelopment, models of computation, parallel and distributed computing, semantics and logics of programs, theoretical issues in artificial intelligence, type theory, VLSI systems. The scientific program will include invited lectures covering the areas of main interest and short original communications. PROGRAM COMMITTEE ----------------- K.R. Apt (The Netherlands), R. Back (Finland), J.C.M. Baeten (The Netherlands), M. Crochemore (France), D. Gabbay (UK), M.C. Gaudel (France), U. Goltz (Germany), W. Forys (Poland), R. Kurshan (USA), W. Marek (USA), I. Nemeti (Hungary), R. De Nicola (Italy), M. Nielsen (Denmark), E.R. Olderog (Germany), E. Orlowska (Poland), Z. Pawlak (Poland), W. Penczek (chair, Poland), A. Pnueli (Israel), G. Rozenberg (The Netherlands), P. Ruzicka (Slovak Republic), W. Rytter (Poland), C. Stirling (UK), A. Szalas (co-chair, Poland), A. Tarlecki (Poland), I. Wegener (Germany), J. Zlatuska (Czech Republik). INVITED SPEAKERS ---------------- E. Clarke (USA), V. Diekert (Germany), A. Gibbons (UK), P. Mosses (Denmark), D. Peled (USA), J. Remmel (USA), D. Sannella (UK) P.S. Thiagarajan (India), J. Tiuryn (Poland), V. Uspensky (Russia). SYMPOSIUM PROGRAM ------------------ Sunday, September 1 18.30--19.30 DINNER Monday, September 2 7.30--8.30 BREAKFAST 8.50 Opening of MFCS'96 9.00--10.00 Invited Talk: (Chairman W. Penczek) Word level model checking E. M. Clarke, Jr. (USA) 10.00--10.30 Coffee Break 10.30--12.10 Session I: A class of information logics with a decidable validity problem S. Demri (France) A modal logic for data analysis P. Balbiani (France) On saturation with flexible function symbols R. Pliuskevicius (Lithuania) Logic of predicates with explicit substitutions M. Bednarczyk (Poland) 12.30--13.30 LUNCH 14.00--15.00 Invited Talk: (Chairman M. Crochemore) Models of DNA computation A. Gibbons (UK) 15.00-15.30 Coffee Break 15.30--16.45 Session II: On the conjugation of standard morphisms P. Seebold (France) On the equivalence problem for E-pattern languages E. Ohlebusch (Germany), E. Ukkonene (Finland) Automaticity III: Polynomial automaticity, context-free languages, and fixed points of morphisms J. Shallit (Canada), I. Glaister (Canada) 16.45--17.00 Break 17.00--17.50 Session III: Approximating good simultaneous diophantine approximations is almost NP-hard J.P. Seifert (Germany), C. Rossner (Germany) (poly(log(log(n))), poly(log(log(n))))-restricted verifiers are unlikely to exist for languages in NP D. Fotakis (Greece), P. Spirakis (Greece) 19.00--22.00 WELCOME PARTY Tuesday, September 3 7.30--8.50 BREAKFAST 9.00--10.00 Invited Talk: (Chairman P. Ruzicka) Code problems on traces V. Diekert (Germany) 10.00--10.30 Coffee Break 10.30--12.10 Session I: On the power of nonconservative PRAM A. Lingas (Sweden), A. Dessmark (Sweden) Parallel alternating-direction access machine B. S. Chlebus, A. Czumaj, L. Gasieniec, M. Kowaluk, W. Plandowski (Poland) Polynomial time samplable distributions T. Yamakami (Canada) Minimizing congestion of layouts for ATM networks with faulty links L. Gasieniec (Poland), E. Kranakis, D. Krizanc, A. Pelc (Canada) 12.30--13.30 LUNCH 14.00--15.00 Invited Talk: (Chairman W. Forys) Mind the gap! ``Semantic'' versus ``syntactic'' models of specifications D. Sannella (UK) 15.00--15.30 Coffee Break 15.30--16.45 Session II: >From specifications to programs: A fork algebraic-approach to bridge the gape G.A. Baum (Argentina), M. Frias (Brasil), A.M. Haeberer (Brasil), P.E.M. Lopez (Argentina) Equational properties of iteration in algebraically complete categories Z. Esik (Hungary), A. Labella (Italy) >From static to dynamic abstract data-types E. Zucca (Italy) 16.45--17.00 Break 17.00--17.50 Session III: On the query complexity of sets R. Beigel (USA), W. Gasarch (USA), M. Kummer (Germany), G. Martin (USA), T. McNicholl (Canada), F. Stephan (Germany) A uniform analysis of trie structures that store prefixing-keys with application to doubly-chained prefixing-tries P. de la Torre, D.T. Kao (UK) 18.30--19.30 DINNER Wednesday, September 4 7.30--8.50 BREAKFAST 9.00--10.00 Invited Talk: (Chairman A. Szalas) Theory and practice of action semantics P.D. Mosses (Denmark) 10.00--10.30 Coffee Break 10.30--12.10 Session I: Causal testing U. Goltz, H. Wehrheim (Germany) Probabilistic metric semantics for a simple language with recursion M. Kwiatkowska, G. Norman (UK) Bisimilarity problems requiring exponential time M. Boreale, L. Trevisan (Italy) Linear dynamic Kahn networks are deterministic A. de Bruin, S. Nienhuys-Cheng (The Netherlands) 12.30--13.30 LUNCH 14.00--15.00 Invited Talk: (Chairman B. Kurshan) Partial order reduction: model-checking using representatives D. Peled (USA) 15.00--15.30 Coffee Break 15.30--16.45 Session II: Simulation of specification statements in Hoare Logic K. Engelhardt, W.-P. de Roever (Germany) Specification and verification of timed lazy systems F. Corradini (UK), M. Pistore (Italy) Specifying and verifying parametric processes W. Pawlowski, P. Paczkowski, S. Sokolowski (Poland) 16.45-17.00 Break 17.00--17.50 Session III: Dynamic graphs A. Maggiolo-Schettini (Italy), J. Winkowski (Poland) On unconditional transfer H. Fernau (Germany) 18.30--19.30 DINNER Thursday, September 5 7.30--8.50 BREAKFAST 9.00--10.00 Invited Talk: (Chairman A. Tarlecki) A sequent calculus for subtyping polymorphic types J. Tiuryn (Poland) 10.00--10.30 Coffee Break 10.30--12.10 Session I: Routing on triangles, tori and honeycombs J. Sibeyn (Germany) Equations on trees S. Mantaci, A. Restivo (Italy) Shortest path problems with time constraints X. Cai (Hong Kong), T. Kloks (The Netherlands), C.K. Wong (Hong Kong) Self-similarity viewed as a local property via tile sets B. Durand (France) 12.10--12.20 Break 12.20--13.20 Invited Talk: Nonmonotonic rule systems: foward chaining, constraints, and complexity. J. Remmel (USA) 13.40--14.30 LUNCH 15.00--21.00 A TRIP TO WIELICZKA AND CONFERENCE BANQUET. Friday, September 6 7.30--8.50 BREAKFAST 9.00--10.00 Invited Talk: (Chairman J. Zlatuska) Linear time temporal logics over Mazurkiewicz traces P.S. Thiagarajan (India) 10.00-10.30 Coffee Break 10.30--12.10 Session I: On fairness in terminating and reactive programs A. Wabenhorst (UK) A lambda calculus of incomplete objects V. Bono, M. Bugliesi, L. Liquori (Italy) A semantic matching algorithm: analysis and implementation H. Shi (Germany) Construction of list homomorphisms by tupling and fusion Z. Hu, H. Iwasaki, M. Takeichi (Japan) 12.10--12.20 Break 12.20--13.20 Invited Talk: Recent moscow works on Kolmogorov complexity V. Uspensky (Russia) 13.40--14.30 LUNCH REGISTRATION ------------ REGISTRATION DESK The registration desk will be open at the symposium center on Sunday, September 1, from 2.00 p.m. to 10.00 p.m. Monday, September 2, from 8.00 a.m. to 12.30 p.m. REGISTRATION FEE The registration fee covers conference fee, accommodation, lunches dinners, coffee breaks, events (a sightseeing tour of Cracow, welcome party, a trip to Wieliczka, conference banquet) and a copy of the proceedings. Early registration (before June 30) - 580 US$ Late registration (after June 30) - 700 US$ There will be some financial support for participants from Eastern Europe awarded on an individual basis. It will cover a part of registration fee. Please indicate in the registration form whether you want to apply. Please use the registration form provided at the end. ACCOMPANYING PERSONS The fee for an acompanying person covers accommodation, lunches, dinners and welcome party. Before June 30 - 350 US$ After June 30 - 430 US$ Extras A trip to Wieliczka and conference banquet - 40 US$ Sightseeing tour of Cracow - 5 US$ PROCEEDINGS The proceedings of the symposium will be published by Springer-Verlag as a volume of Lecture Notes in Computer Science. Each registered participant will receive one copy upon registration. Additional copies may be ordered directly from Springer Verlag. In case of cancellation, a copy of the proceedings may be sent by mail. CANCELLATION Cancellation received later than 20 July will be charged US$ 100 handling fee. No cancellations will be accepted after 15 August. PAYMENT By Banker's Cheque payable to "IPI PAN MFCS'96" (personal cheques will not be accepted) or by bank transfer to: Bank Przemyslowo-Handlowy Krakow XIV O/W-wa, Al. Jerozolimskie 7, 00-495 Warsaw, Poland Account no. 320007-2408 You may pay at the site in cash or by any of the major credit cards (Visa, MasterCard, EuroCard, Access, Diners Club). You will be charged then an additional 5% of bank commission. GENERAL INFORMATION ------------------- LOCATION Cracow is the old capital of Poland. It attracts numerous tourists >From all over the world who are eager to see its magnificent art treasures. The symposium will be organized in the POLONIA INSTITUTE of the Jagiellonian University (address in Polish: Jodlowa 13, Krakow-Przegorzaly), situated in a beautiful rural area on the outskirts of Cracow, on a wooded hill overlooking the picturesque valley of the Vistula river. TRAVEL Although Cracow has an international airport there are few international flights. You may need to fly to Warsaw and then take a domestic flight to Cracow or switch to train. To get to Warsaw Central Railway Station (Warszawa Centralna) from the Warsaw airport, take a bus or a taxi. Taxi fare should not exceed 25 zlotys (approx. 10 $). A one-way (InterCity) train ticket from Warsaw to Cracow should cost about 50 zlotys (20 $). The InterCity train takes 2h40m. On Sunday, September 1, a shuttle bus will be available on the route Cracow airport - Cracow train station - conference center. Advise the organisers on your arrival time so the bus can be scheduled accordingly. ACCOMMODATION The participants will be accommodated directly at the conference center. There are only double rooms. All rooms have private bathrooms. POLISH CURRENCY Polish currency units are zloty (PLN) and grosz (1 grosz = 1/100 zloty). There was a denomination on January 1, 1995, and at present there are both old and new zlotys in the circulation. 1 new zloty = 10,000 old zlotys. All coins are new (1, 2, 5, 10, 20, 50 groszy and 1, 2, 5 zlotys) but there are TWO kinds of notes. 10, 20, 50 and 200 zloty notes are new. Unfortunatelly, there are old and new 100 zloty notes. The old one (red in colour) is worth just 1 grosz. MONEY EXCHANGE As most payments are made in cash in Poland, you are advised to exchange some money. This can be done at exchange offices (usually called "kantor"), which can be found almost everywhere (e.g. at the airport or at the railway stations). Current exchange rates (as for ...) are 2.62 PLN = 1 US$ and 1.74 PLN = 1 DM. VISAS Citizens of most European countries and the U.S. do not need a visa. Check with your local Polish consulate if you need one. CLIMATE Daytime and nighttime temperatures in early September are expected to be 13-18 and 8-13 degrees Celsius, respectively. It might rain, but the weather is usually nice. HOTEL RESERVATION (WARSAW) If you need hotel reservation in Warsaw contact the organisers directly. SOCIAL PROGRAM Sunday, September 1, from 3 p.m. to 5 p.m. sightseeing tour of Cracow. Monday, September 2, at 6.30 p.m. welcome party at the conference center Thursday, September 5, from 3 p.m. to 9 p.m. a trip to Wieliczka and conference banquet ORGANIZING COMMITTEE -------------------- S. Ambroszkiewicz, M. Bialasik, W. Forys, E. Gasiorowska, B. Konikowska (chair), W. Penczek, M. Srebrny, A. Szalas, A. Tarlecki. FURTHER INFORMATION All enquiries should be sent to Beata Konikowska, Institute of Computer Science, Polish Academy of Sciences, ul. Ordona 21, 01-237 Warsaw, Poland; e-mail: beatak@ipipan.waw.pl or mfcs96@ipipan.waw.pl, tel. +48 22 36 28 41, fax: +48 22 37 65 64. Additional information can be ftp'ed from 'anonymous' ftp.ipipan.waw.pl, from the directory pub/conferences/mfcs96. It is also available at http://www.ipipan.waw.pl/conferences/mfcs96. The symposium is organized by the Institute of Computer Science, Polish Academy of Sciences in co-operation with the Institute of Informatics, Warsaw University. MFCS'96 is supported by the European Association for Theoretical Computer Science (EATCS), ICS PAS, Warsaw University, European MEDICIS project, Microsoft Poland, SUN Poland, and State Committee for Scientific Research. REGISTRATION FORM ----------------- If you would like to register for MFCS'96, please return the following information (preferably by e-mail) to: Beata Konikowska MFCS'96 Institute of Computer Science Polish Academy of Sciences ul. Ordona 21, 01-237 Warsaw, Poland e--mail: beatak@ipipan.waw.pl or mfcs96@ipipan.waw.pl ---------------------------------------------------------------------- First Name: ......................................................... Family Name: ......................................................... Prof. Dr. Mr. Ms.: ................................................... Affiliation: ......................................................... Address: .........................Tel.: ........................ ........................ Fax: ........................ .........................E-mail: ........................ Your identification as it should appear on your badge: ......................................................... ......................................................... ---------------------------------------------------------------------- Means of travel: .................................................... Date of arrival to Cracow: ........... approximate time: ......... Date of departure from Cracow: ........... approximate time: ......... Diet: Standard* Vegetarian* *) Delete where non applicable ______________________________________________________________________ ACCOMODATION: I would like to share a room with .................................... ---------------------------------------------------------------------- Registration fees (all fees in US$) BEFORE AFTER June 30, 1996 June 30, 1996 Registration fee: 580 US$ 700 US$ Registration fee: 575 US$ 695 US$ (not including a sightseeing tour of Cracow) Accompanying person fee: 350 US$ 430 US$ Trip to Wieliczka and conference banquet: 40 US$ 40 US$ Sightseeing tour of Cracow: 5 US$ 5 US$ Total amount: .... US$ .... US$ ______________________________________________________________________ I would like to apply for a financial support ........................ (only applicable to participants from Eastern Europe) ---------------------------------------------------------------------- Method of payment: ( ) I enclose a copy of bank transfer to: Bank Przemyslowo-Handlowy Krakow XIV O/W-wa, Al. Jerozolimskie 7, 00-495 Warsaw, Poland Account no. 320007-2408 ( ) I enclose a Banker's Cheque payable to "IPI PAN MFCS'96" for the total amount of ..... US$ net of bank charges ( ) I will pay at the site: ( ) in cash ( ) by credit card ---------------------------------------------------------------------- IF YOU PAY BY CREDIT CARD BEFORE CONFERENCE, PLEASE FILL IN THE FORM BELOW AND SEND IT IMMEDIATELY BY * FAX * (we need your signature) Mail order Method of payment - charge credit card Name of card: ............................................. Card number: ............................................. Expiry date: ............................................. Name of cardholder: ............................................. Address of cardholder: ............................................. Signature of cardholder: ............................................. Service specification: ............................................. ----------------------------------------------------------------------