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.

**Invited speakers**: *S. Abramsky (UK), L. Babai (USA), H.L. Bodlaender
(The Netherlands), N. Dershowitz (USA), C. Dwork (USA), J. Hromkovic (Slovakia),
J. Krajicek (Czech Republic), U. Montanari (Italy), R. Reischuk (Germany),
D. Roth (Israel), U. Schoening (Germany)*.

**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.

**9:00***L. Babai (Chicago):*Communication Complexity**(Invited Lecture)****9:50***C. Dwork (San Jose):*Positive Uses of Lattices in Cryptography**(Invited Lecture)****10:40**- Break

**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**- Lunch

**14:15***U. Montanari (Menlo Park and Pisa, joint work with G. L. Ferrari):*A Tile-Based Coordination View of Pi-Calculus**(Invited 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**- Break

**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**- End of Session

**19:00**- Welcome Party
## Tuesday, August 26

**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**- Break

**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**- Lunch

**14:15***S. Abramsky (London):*Game Semantics for Programming Languages**(Invited 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**- Break

**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**- End of Session

## Wednesday, August 27

**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 and Jerusalem):*When are Two Rewrite Systems More than None?**(Invited Lecture)****10:40**- Break

**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**- Lunch

**13:00**- Excursion
## Thursday, August 28

**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**- Break

**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**- Lunch

**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**- Break

**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**- End of Session

**18:30**- Conference Dinner
## Friday, August 29

**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**- Break

**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**- Lunch

- End of MFCS'97