From - Sun Jun 22 15:41:55 1997 Newsgroups: comp.theory Path: Radon.Stanford.EDU!news.Stanford.EDU!su-news-hub1.bbnplanet.com!news.bbnplanet.com!feeder.chicago.cic.net!howland.erols.net!EU.net!sk2eu!news From: duris@dcs.fmph.uniba.sk (Pavol Duris) Subject: Cfp MFCS'97 (ASCII) Message-ID: Followup-To: news.uakom.sk Sender: news@sk2eu.eunet.sk (News Administrator) Reply-To: duris@dcs.fmph.uniba.sk Organization: Faculty of Math. and Physics, Comenius Univ., Bratislava, Slovakia Date: Tue, 17 Jun 1997 07:58:53 GMT Lines: 571 Xref: Radon.Stanford.EDU comp.theory:11980 X-Mozilla-Status: 0001 Content-Length: 14886 C A L L F O R P A R T I C I P A T I O N (ASCII Version) MM MM FFFFFFFF CCCCCCCC SSSSSSSS '' 99999999 77777777 MMM MMM FF CC SS '' 99 99 77 MMMMMMMM FFFFF CC SSSSSSSS 99999999 77 MM MM MM FF CC SS 99 77 MM MM FF CCCCCCCC SSSSSSSS 99999999 77 The 22nd International Symposium on Mathematical Foundations of Computer Science August 25-29, 1997 Bratislava, Slovakia The International Symposium on Mathematical Foundations of Computer Science is the 22nd in the series of MFCS symposia organized alternately in the Czech Republic, Poland and Slovakia. The MFCS symposia encourage high-quality research in all branches of theoretical computer science. Their broad scope provides an opportunity to bring together specialists who do not usually meet at specialized conferences. Principal topics of interest include (but are not limited to): algorithms and data structures, automata and formal languages, complexity and computability, concurrency theory, computational geometry, cryptography and security, data bases and knowledge-based systems, foundations of declarative programming, formal specifications and program development, models of computation, parallel and distributed computing, semantics and logics of programs, theoretical issues in artificial intelligence. The symposium is organized by the Slovak Society for Computer Science and the Comenius University in Bratislava in cooperation with other institutions in Slovakia, and is supported by the European Association for Theoretical Computer Science. P r o g r a m C o m m i t t e e G. Ausiello (Italy) W. Penczek (Poland) J. Diaz (Spain) V. Pratt (USA) P. Duris (Slovakia) I. Privara (co-chair, Slovakia) T. Eiter (Austria) B. Rovan (Slovakia) R. Freivalds (Latvia) P. Ruzicka (chair, Slovakia) F. Gecseg (Hungary) A. Salwicki (Poland) J. Karhumaki (Finland) D. Sotteau (France) H. Kirchner (France) J. van Leeuwen (The Netherlands) H.-J. Kreowski (Germany) J. Wiedermann (Czech Republic) F. Meyer auf der Heide (Germany) J. Zlatuska (Czech Republic) M. Nielsen (Denmark) S c i e n t i f i c P r o g r a m In accordance with tradition the scientific program will include 11 invited lectures covering the areas of current interest and 40 short communications describing original research selected by the Program Committee from 94 submitted papers. P r o c e e d i n g s The conference proceedings are published by Springer-Verlag in the series "Lecture Notes in Computer Science" and distributed at the conference. Additional copies may be ordered directly from Springer-Verlag. L o c a l A r r a n g e m e n t s MFCS'97 Organizing Committee Pavol Duris Department of Computer Science Comenius University 842 15 Bratislava, Slovakia tel: ++(421) (7) 726 63 fax: ++(421) (7) 727 041 e-mail: mfcs97@dcs.fmph.uniba.sk * * * P R O G R A M * * * S u n d a y, A u g u s t 2 4 14:00 - 22:00 Registration M o n d a y, A u g u s t 2 5 8:45 Opening of MFCS'97 Session 1. Chair: J. van Leeuwen (Utrecht) 9:00 L. Babai (Chicago): Communication Complexity (Invited Lecture) 9:50 C. Dwork (San Jose): Positive Uses of Lattices in Cryptography (Inited Lecture) 10:40 --- B r e a k --- 11:05 D. Krznaric (Lund), C. Levcopoulos (Lund): Optimal Algorithms for Complete Linkage Clustering in d Dimensions 11:30 S. Jukna (Trier), A. Razborov (Moscow), P. Savicky (Prague), I. Wegener (Dortmund): On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs 11:55 B. Bollig (Dortmund), I. Wegener (Dortmund): Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams 12:20 M. Mundhenk (Trier): NP-hard Sets Have Many Hard Instances 12:45 --- L u n c h --- Session 2. Chair: A. Salwicki (Pau and Warsaw) 14:15 U. Montanari (Menlo Park and Pisa, joint work with G. L. Ferrari): A Tile-Based Coordination View of Pi-Calculus (Inited Lecture) 15:05 F. Afrati (Athens), I. Guessarian (Paris), M. de Rougemont (Paris): The Expressiveness of Datalog Circuits (DAC) 15:30 J. Tyszkiewicz (Aachen): Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines 15:55 --- B r e a k --- 16:20 B. Berard (Cachan), C. Picaronny (Cachan): Accepting Zeno Words without Stopping Time 16:45 A. Rensink (Hildesheim), H. Wehrheim (Hildesheim): Dependency-based Action Refinement 17:10 W. Vogler (Augsburg): Partial Order Semantics and Read Arcs 17:35 Z. Khasidashvili (Atsugi), J. Glauert (Norwich): Relating Conflict-free Stable Transition and Event Models 18:00 --- E n d o f S e s s i o n --- 19:00 Welcome Party T u e s d a y, A u g u s t 2 6 Session 3. Chair: G. Mirkowska (Pau and Warsaw) 9:00 J. Krajicek (Prague): Trends, Problems and Examples in Proof Complexity (Invited Lecture) 9:50 B. Heinemann (Hagen): A Topological Generalization of Propositional Linear Time Temporal Logic 10:15 G. Chen (Paris): Subtyping Calculus Construction - Type Conversion and Transitivity Elimination 10:40 --- B r e a k --- 11:15 M. Mundhenk (Trier), J. Goldsmith (Lexington), E. Allender (New Brunswick): The Complexity of Policy Evaluation for Finite-horizon Partially-observable Markov Decision Processes 11:30 J. F. Sibeyn (Saarbrucken): Routing with Finite Speeds of Memory and Network 11:55 C. Gavoille (Bordeaux): On Dilation of Interval Routing 12:20 A. Goerdt (Chemnitz): The Giant Component Threshold for Random Regular Graphs with Edge Faults 12:45 --- L u n c h --- Session 4. Chair: H.-J. Kreowski (Bremen) 14:15 S. Abramsky (London): Game Semantics for Programming Languages (Inited Lecture) 15:05 R. Heckel (Berlin), H. Ehrig (Berlin), U. Wolter (Berlin), A. Corradini (Amsterdam): Integrating the Specification Techniques of Graph Transformation and Temporal Logic 15:30 M. M. Bonsangue (Leiden), J. N. Kok (Leiden): Specifying Computations Using Hyper Transition Systems 15:55 --- B r e a k --- 16:20 G. Karner (Wien), W. Kuich (Wien): A Characterization of Abstract Families of Algebraic Power Series 16:45 Y. Kobayashi (Funabashi), F. Otto (Kassel): Repetitiveness of D0L-Languages is Decidable in Polynomial Time 17:10 C. Choffrut (Paris), G. Pighizzini (Milano): Distances between Languages and Reflexivity of Relations 17:35 R. Kolpakov (Moscow), G. Kucherov (Villers-les-Nancy): Minimal Letter Frequency in n-th Power-free Binary Words 18:00 --- E n d o f S e s s i o n --- W e d n e s d a y, A u g u s t 2 7 Session 5. Chair: J. Zlatuska (Brno) 9:00 K. R. Reischuk (Lubeck and Kyushu, joint work with M. Liskiewicz): Computational Limitations of Stochastic Turing Machines and Arthur-Merlin Games with Small Space Bounds (Invited Lecture) 9:50 N. Dershowitz (Urbana): When are Two Rewrite Systems More than None? (Invited Lecture) 10:40 --- B r e a k --- 11:05 D. Plump (Bremen): Simplification Orders for Term Graph Rewriting 11:30 W. Fokkink (Swansea), J. van de Pol (Eindhoven): Simulation as a Correct Compilation of Rewrite Systems 11:55 --- L u n c h --- 13:00 Excursion T h u r s d a y, A u g u s t 2 8 Session 6. Chair: J. Wiedermann (Prague) 9:00 U. Schoning (Ulm): Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity (Invited Lecture) 9:50 K. Iwama (Fukuoka): Complexity of Finding Short Resolution Proofs 10:15 K. Meer (Aachen): Counting Problems over the Reals 10:40 --- B r e a k --- 11:05 Ch. Meinel (Trier), T. Theobald (Trier): On the Influence of the State Encoding on OBDD-Representations of Finite State Machines 11:30 P. Savicky (Prague), S. Zak (Prague): A Hierarchy for (1,+k)-branching Program with Respect to k 11:55 G. Manzini (Torino), L. Margara (Bologna): Invertible Linear Cellular Automata over Z_m: Algorithmic and Dynamical Aspects 12:20 I. Korec (Bratislava): Real-time Generation of Primes by a One-dimensional Cellular Automaton with 11 States 12:45 --- L u n c h --- Session 7. Chair: J. Karhumaki (Turku) 14:15 J. Hromkovic (Aachen, joint work with G. Schnitger): Communication Complexity and Sequential Computation (Invited Lecture) 15:05 M. Holzer (Tubingen): Multi-Head Finite Automata: Data-Independent versus Data-Dependent Computations 15:30 F. Drewes (Bremen): On the Generation of Trees by Hyperedge Replacement 15:55 --- B r e a k --- 16:20 R. Meyer (Cachan), A. Petit (Cachan): Decomposition of TrPTL Formulas 16:45 I. Ryl (Lille), Y. Roos (Lille), M. Clerbout (Lille): Partial Characterization of Synchronization Languages 17:10 L. Bernardinello (Milano), L. Pomello (Milano): A Category of Transition Systems and its Relations with Orthomodular Posets 17:35 G. Cattaneo (Milano), E. Formenti (Lyon), L. Margara (Bologna), J. Mazoyer (Lyon): A Shift-invariant Metric on S^Z Inducing a Non-trivial Topology 18:00 --- E n d o f S e s s i o n --- 18:30 Conference Dinner F r i d a y, A u g u s t 2 9 Session 8. Chair: W. Kuich (Wien) 9:00 D. Roth (Rehovot): Learning to Perform Knowledge-intensive Inferences (Invited Lecture) 9:50 H. Bodlaender (Utrecht): Treewidth: Engineering Algorithms (Invited Lecture) 10:40 --- B r e a k --- 11:05 C. Martin-Vide (Tarragona), J. Miquel-Verges (Tarragona), G.Paun (Bucuresti): Two-level Contextual Grammars: The Internal Case 11:30 H. Fernau (Tubingen), R. Stiebe (Halle): Regulation by Valences 11:55 H. Petersen (Stuttgart): Homomorphic Images of Sentential Forms and Terminating Grammars 12:20 A. Nickelsen (Berlin): Deciding Verbose Languages with Linear Advice 12:45 --- L u n c h --- ----------------------------- End of MFCS'97 ----------------------------- R e g i s t r a t i o n F e e The registration fee covers conference fee, accommodation (double room), breakfasts, lunches, coffee breaks, events (welcome party, a bus trip to the Cerveny Kamen castle, conference dinner) and a copy of the proceedings. Early registration (before July 15) EATCS members 420 US$ non-members 440 US$ Late registration (after July 15) EATCS members 460 US$ non-members 480 US$ Single occupancy in double room will be available for a limited number of participants for 35 US$ extra charge. A c c o m p a n y i n g P e r s o n s The fee for an accompanying person covers accommodation (double room), breakfasts, lunches, welcome party, a bus trip to the Cerveny Kamen castle and conference dinner. Early registration 220 US$ Late registration 240 US$ Additional program for accompanying persons is offered (provided there is a sufficient interest). P a y m e n t Please transfer the equivalent of your registration and accommodation fee to the following bank account of the Slovak Society for Computer Science Tatra Banka, a.s., Bratislava ACCOUNT NUMBER: 2667000067/1100 SWIFT CODE: TATR SK BX MFCS Please make sure that your payment carries your name, quotes "MFCS" as suggested, and arrives free of bank charges. To speed-up the registration procedure, please, transfer your fee via one of the correspondent banks of Tatra Banka (listed below). *** Correspondent Banks of Tatra Banka *** ATS RZB, Wien RZBA AT WW RLB NOE, Wien RLNW AT WW Bank Austria, Wien BKAU AT WW AUD ANZ Bank, Melbourne ANZB AU 3M BEF Generale Bank, Brussels GEBA BE BB CAD Royal Bank of Canada, Toronto ROYC CA T2 CHF Union Bank of Switzerland, Zurich UBSW CH ZH Credit Swiss First Boston, Zurich CRES CH ZZ CZK Komercni Banka, Praha KOMB CZ PP Commerzbank, Praha COBA CZ PX Raiffeisenbank, Praha RZBC CZ PP DEM DG Bank, Frankfurt a/M GENO DE FF Commerzbank, Frankfurt a/M COBA DE FF Deutsche Bank, Frankfurt a/M DEUT DE FF Vereinsbank, Munchen BVBE DE MM WGZ Bank, Dusseldorf GENO DE DD DKK Den Danske Bank, Copenhagen DABA DK KK ESP Banco Bilbao Vizcaya, Madrid BBVI ES MM FIM Merita Bank, Helsinki MRIT FI HH FRF Credit Agricole, Paris AGRI FR PP Societe Generale, Paris SOGE FR PP Banque Rivaud, Paris RUBB FR PP GBP Midland Bank, London MIDL GB 22 Barclays Bank, London BARC GB 22 IEP Allied Irish Banks, Dublin AIBK IE 2D ITL Banca Nazionale del Lavoro, Roma BNLI IT RR Credito Italiano, Milano CRIT IT MM Banco Ambrosiano Veneto, Milano BAVE IT MM JPY Bank of Tokyo-Mitsubishi, Tokyo BOTK JP JT NLG ABN.AMRO Bank, Amsterdam ABNA NL 2A NOK Den norske Bank, Oslo DNBA NO KK SEK Svenska Handelsbanken, Stockholm HAND SE SS USD Bankers Trust, New York BKTR US 33 AMEX, New York AEIB US 33 XEU Generale Bank, Brussels GEBA BE BB L o c a t i o n Bratislava (population 450 000) is the capital of Slovak Republic, located close to the Austrian, Hungarian and Czech borders. Bratislava is a very old town with more than 2000 years history. Full town privileges were granted to Bratislava in 1291. The historic centre is dominated by the Bratislava Castle. Today Bratislava is a political, economic and cultural centre of Slovakia. Bratislava is the seat of Comenius University, Slovak Technical University and Economy University. C o n f e r e n c e S i t e The conference will be held in Druzba - congress centre of the Comenius University (Botanicka 25, 842 15 Bratislava, Slovakia), which is located about 3 km west of the town centre. By regular tram connections it is possible to reach the town centre in about 10 minutes. E n t r y V i s a Citizens of most European countries do not need entry visa. As the visa regulations keep changing, please check with the nearest Slovak Consulate whether you need a visa. Note that processing your visa application may take several weeks. G e t t i n g T h e r e Only few international flights land at the Bratislava airport. The nearest large international airports are Vienna (Austria), Prague (Czech Republic) and Budapest (Hungary).