MFCS'97: Program
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.
Sunday, August 24
14:00 - 22:00Registration
Monday, August 25
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 (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
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 (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
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
- 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
Session 4. Chair: H.-J. Kreowski (Bremen)
- 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
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 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
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
- 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
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
- 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
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
- 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
Back to the MFCS'97 Main Page