22. MFCS 1997: Bratislava, Slovakia

@proceedings{DBLP:conf/mfcs/1997,
  editor    = {Igor Pr\'{\i}vara and
               Peter Ruzicka},
  title     = {Mathematical Foundations of Computer Science 1997, 22nd International
               Symposium, MFCS'97, Bratislava, Slovakia, August 25-29, 1997,
               Proceedings},
  booktitle = {MFCS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1295},
  year      = {1997},
  isbn      = {3-540-63437-1},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Papers

• Samson Abramsky: Game Semantics for Programming Languages (Abstract). 3-4 BibTeX
• László Babai: Communication Complexity. 5-18 BibTeX
• Hans L. Bodlaender: Treewidth: Algorithmoc Techniques and Results. 19-36 BibTeX
• Nachum Dershowitz: When are Two Rewrite Systems More than None? 37-43 BibTeX
• Cynthia Dwork: Positive Applications of Lattices to Cryptography. 44-51 BibTeX
• Gian Luigi Ferrari, Ugo Montanari: A Tile-Based Coordination View of Asynchronous pi-Calculus. 52-70 BibTeX
• Juraj Hromkovic, Georg Schnitger: Communication Complexity and Sequential Compuation. 71-84 BibTeX
• Jan Krajícek: Lower Bounds for a Proof System with an Expentential Speed-up over Constant-Depth Frege Systems and over Polynomial Calculus. 85-90 BibTeX
• Maciej Liskiewicz, Rüdiger Reischuk: Computational Limitations of Stochastic Turing Machines and Arthur-Merlin Games with Small Space Bounds. 91-107 BibTeX
• Dan Roth: Learning to Perform Knowledge-Intensive Inferences. 108-109 BibTeX
• Uwe Schöning: Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity. 110-116 BibTeX

Contributed Papers

• Foto N. Afrati, Irène Guessarian, Michel de Rougemont: The Expressiveness of Datalog Circuits (DAC). 119-128 BibTeX
• Martin Mundhenk, Judy Goldsmith, Eric Allender: The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes. 129-138 BibTeX
• Luca Bernardinello, Lucia Pomello: A Category of Transition Systems and Its Relations with Orthomodular Posets. 139-148 BibTeX
• Béatrice Bérard, Claudine Picaronny: Accepting Zeno Words Without Making Time Stand Still. 149-158 BibTeX
• Beate Bollig, Ingo Wegener: Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams. 159-168 BibTeX
• Marcello M. Bonsangue, Joost N. Kok: Specifying Computations Using Hyper Transition Systems. 169-178 BibTeX
• Gianpiero Cattaneo, Enrico Formenti, Luciano Margara, Jacques Mazoyer: A Shift-Invariant Metric on S^zz Inducing a Non-trivial Tolology. 179-188 BibTeX
• Gang Chen: Subtyping Calculus of Construction (Extended Abstract). 189-198 BibTeX
• Christian Choffrut, Giovanni Pighizzini: Distances Between Languages and Reflexivity of Relations. 199-208 BibTeX
• Isabelle Ryl, Yves Roos, Mireille Clerbout: Partial Characterization of Synchronization Languages. 209-218 BibTeX
• Reiko Heckel, Hartmut Ehrig, Uwe Wolter, Andrea Corradini: Integrating the Specification Techniques of Graph Transformation and Temporal Logic. 219-228 BibTeX
• Frank Drewes: On the Generation of Trees by Hyperedge Replacement. 229-238 BibTeX
• Henning Fernau, Ralf Stiebe: Regulations by Valences. 239-248 BibTeX
• Wan Fokkink, Jaco van de Pol: Simulation as a Correct Transformation of Rewrite Systems. 249-258 BibTeX
• Cyril Gavoille: On the Dilation of Interval Routing. 259-268 BibTeX
• Zurab Khasidashvili, John R. W. Glauert: Relating Conflict-Free Stable Transition and Event Models (Extended Abstract). 269-278 BibTeX
• Andreas Goerdt: The Giant Component Threshold for Random Regular Graphs with Edge Faults. 279-288 BibTeX
• Bernhard Heinemann: A Topological Generalization of Propositional Linear Time Temporal Logic. 289-297 BibTeX
• Markus Holzer: Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations. 299-308 BibTeX
• Kazuo Iwama: Complexity of Finding Short Resolution Proofs. 309-318 BibTeX
• Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener: On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs. 319-326 BibTeX
• Georg Karner, Werner Kuich: A Characterization of Abstract Families of Algebraic Power Series. 327-336 BibTeX
• Yuji Kobayashi, Friedrich Otto: Repetitiveness of D0L-Languages Is Decidable in Polynomial Time. 337-346 BibTeX
• Roman M. Kolpakov, Gregory Kucherov: Minimal Letter Frequency in n-th Power-Free Binary Words. 347-357 BibTeX
• Ivan Korec: Real-Time Generation of Primes by a One-Dimensional Cellular Automaton with 11 States. 358-367 BibTeX
• Drago Krznaric, Christos Levcopoulos: Optimal Algorithms for Complete Linkage Clustering in d Dimensions. 368-377 BibTeX
• Giovanni Manzini, Luciano Margara: Invertible Linear Cellular Automata over z_m: Algorithmic and Dynamical Aspects. 378-387 BibTeX
• Carlos Martín-Vide, Joan Miquel-Verges, Gheorghe Paun: Two-Level Contextual Grammars: The Internal Case. 388-397 BibTeX
• Klaus Meer: Counting Problems over the Reals. 398-407 BibTeX
• Christoph Meinel, Thorsten Theobald: On the Influence of the State Encoding on OBDD-Representations of Finite State Machines. 408-417 BibTeX
• Raphaël Meyer, Antoine Petit: Decomposition of TrPTL Formulas. 418-427 BibTeX
• Martin Mundhenk: NP-Hard Sets Have Many Hard Instances. 428-437 BibTeX
• Arfst Nickelsen: Deciding Verbose Languages with Linear Advice. 438-447 BibTeX
• Holger Petersen: Homomorphic Images os Sentential Forms and Terminating Grammars (Extended Abstract). 448-457 BibTeX
• Detlef Plump: Simplification Orders for Term Graph Rewriting. 458-467 BibTeX
• Arend Rensink, Heike Wehrheim: Dependency-Based Action Refinement. 468-477 BibTeX
• Petr Savický, Stanislav Zák: A Hierarchy for (1, +k)-Branching Programs with Respect of k. 478-487 BibTeX
• Jop F. Sibeyn: Routing with Finite Speeds of Memory and Network. 488-497 BibTeX
• Jerzy Tyszkiewicz: Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines (Extended Abstract). 498-507 BibTeX
• Walter Vogler: Partial Order Semantics and Read Arcs. 508-517 BibTeX