22. MFCS 1997: Bratislava, Slovakia

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
  
• Juraj Hromkovic, Georg Schnitger:
  Communication Complexity and Sequential Compuation. 71-84
  
• 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
  
• Béatrice Bérard, Claudine Picaronny:
  Accepting Zeno Words Without Making Time Stand Still. 149-158
  
• 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 S^zz 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
  
• Henning Fernau, Ralf Stiebe:
  Regulations by Valences. 239-248
  
• Wan Fokkink, Jaco van de Pol:
  Simulation as a Correct Transformation of Rewrite Systems. 249-258
  
• 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 z_m: 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
  
• Raphaël Meyer, Antoine Petit:
  Decomposition of TrPTL Formulas. 418-427
  
• 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
  
• Arend Rensink, Heike Wehrheim:
  Dependency-Based Action Refinement. 468-477
  
• Petr Savický, Stanislav Zák:
  A Hierarchy for (1, +k)-Branching Programs with Respect of k. 478-487
  
• 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
  

Last update Tue Feb 14 04:07:31 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page