22. MFCS 1997: Bratislava, Slovakia
Igor Prívara, Peter Ruzicka (Eds.): Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS'97, Bratislava, Slovakia, August 25-29, 1997, Proceedings. Springer 1997 Lecture Notes in Computer Science ISBN 3-540-63437-1
Invited Papers
- Samson Abramsky: Game Semantics for Programming Languages (Abstract). 3-4
- László Babai: Communication Complexity. 5-18
- Hans L. Bodlaender: Treewidth: Algorithmoc Techniques and Results. 19-36
- Nachum Dershowitz: When are Two Rewrite Systems More than None? 37-43
- Cynthia Dwork: Positive Applications of Lattices to Cryptography. 44-51
- Gian Luigi Ferrari, Ugo Montanari: A Tile-Based Coordination View of Asynchronous pi-Calculus. 52-70
- 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
- Maciej Liskiewicz, Rüdiger Reischuk: Computational Limitations of Stochastic Turing Machines and Arthur-Merlin Games with Small Space Bounds. 91-107
- Dan Roth: Learning to Perform Knowledge-Intensive Inferences. 108-109
- Uwe Schöning: Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity. 110-116
Contributed Papers
- Foto N. Afrati, Irène Guessarian, Michel de Rougemont: The Expressiveness of Datalog Circuits (DAC). 119-128
- Martin Mundhenk, Judy Goldsmith, Eric Allender: The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes. 129-138
- Luca Bernardinello, Lucia Pomello: A Category of Transition Systems and Its Relations with Orthomodular Posets. 139-148
- Beate Bollig, Ingo Wegener: Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams. 159-168
- Marcello M. Bonsangue, Joost N. Kok: Specifying Computations Using Hyper Transition Systems. 169-178
- Gianpiero Cattaneo, Enrico Formenti, Luciano Margara, Jacques Mazoyer: A Shift-Invariant Metric on Szz Inducing a Non-trivial Tolology. 179-188
- Gang Chen: Subtyping Calculus of Construction (Extended Abstract). 189-198
- Christian Choffrut, Giovanni Pighizzini: Distances Between Languages and Reflexivity of Relations. 199-208
- Isabelle Ryl, Yves Roos, Mireille Clerbout: Partial Characterization of Synchronization Languages. 209-218
- Reiko Heckel, Hartmut Ehrig, Uwe Wolter, Andrea Corradini: Integrating the Specification Techniques of Graph Transformation and Temporal Logic. 219-228
- Frank Drewes: On the Generation of Trees by Hyperedge Replacement. 229-238
- Cyril Gavoille: On the Dilation of Interval Routing. 259-268
- Zurab Khasidashvili, John R. W. Glauert: Relating Conflict-Free Stable Transition and Event Models (Extended Abstract). 269-278
- Andreas Goerdt: The Giant Component Threshold for Random Regular Graphs with Edge Faults. 279-288
- Bernhard Heinemann: A Topological Generalization of Propositional Linear Time Temporal Logic. 289-297
- Markus Holzer: Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations. 299-308
- Kazuo Iwama: Complexity of Finding Short Resolution Proofs. 309-318
- 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
- Georg Karner, Werner Kuich: A Characterization of Abstract Families of Algebraic Power Series. 327-336
- Yuji Kobayashi, Friedrich Otto: Repetitiveness of D0L-Languages Is Decidable in Polynomial Time. 337-346
- Roman M. Kolpakov, Gregory Kucherov: Minimal Letter Frequency in n-th Power-Free Binary Words. 347-357
- Ivan Korec: Real-Time Generation of Primes by a One-Dimensional Cellular Automaton with 11 States. 358-367
- Drago Krznaric, Christos Levcopoulos: Optimal Algorithms for Complete Linkage Clustering in d Dimensions. 368-377
- Giovanni Manzini, Luciano Margara: Invertible Linear Cellular Automata over zm: Algorithmic and Dynamical Aspects. 378-387
- Carlos Martín-Vide, Joan Miquel-Verges, Gheorghe Paun: Two-Level Contextual Grammars: The Internal Case. 388-397
- Klaus Meer: Counting Problems over the Reals. 398-407
- Christoph Meinel, Thorsten Theobald: On the Influence of the State Encoding on OBDD-Representations of Finite State Machines. 408-417
- Martin Mundhenk: NP-Hard Sets Have Many Hard Instances. 428-437
- Arfst Nickelsen: Deciding Verbose Languages with Linear Advice. 438-447
- Holger Petersen: Homomorphic Images os Sentential Forms and Terminating Grammars (Extended Abstract). 448-457
- Detlef Plump: Simplification Orders for Term Graph Rewriting. 458-467
- Jop F. Sibeyn: Routing with Finite Speeds of Memory and Network. 488-497
- Jerzy Tyszkiewicz: Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines (Extended Abstract). 498-507
- Walter Vogler: Partial Order Semantics and Read Arcs. 508-517
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team