21. MFCS 1996: Cracow, Poland

Invited Papers

• Edmund M. Clarke, Xudong Zhao:
  Word Level Model Checking (Abstract). 1
  
• Volker Diekert, Anca Muscholl:
  Code Problems on Traces. 2-17
  
• Alan Gibbons, Martyn Amos, David Hodgson:
  Models of DNA Computation. 18-36
  
• Peter D. Mosses:
  Theory and Practice of Action Semantics. 37-61
  
• Madhavan Mukund, P. S. Thiagarajan:
  Linear Time Temporal Logics over Mazurkiewicz Traces. 62-92
  
• Doron Peled:
  Partial Order Reduction: Model-Checking Using Representatives. 93-112
  
• Jeffrey B. Remmel:
  Nonmonotonic Rule Systems: Foward Chaining, Constraints, and Complexity (Abstract). 113
  
• Donald Sannella, Andrzej Tarlecki:
  Mind the Gap! Abstract Versus Concrete Models of Specifications. 114-134
  
• Jerzy Tiuryn:
  A Sequent Calculus for Subtyping Polymorphic Types. 135-155
  
• Vladimir A. Uspensky:
  Kolmogorov Complexity: Recent Research in Moscow. 156-166
  

Contributed Papers

• Philippe Balbiani:
  A Modal Logic for Data Analysis. 167-179
  
• Gabriel Baum, Marcelo F. Frias, Armando Martin Haeberer, Pablo E. Martínez López:
  From Specifications to Programs: A Fork-Algebraic Approach to Bridge the Gap. 180-191
  
• Marek A. Bednarczyk:
  Logic of Predicates with Explicit Substitutions. 192-205
  
• Richard Beigel, William I. Gasarch, Martin Kummer, Timothy McNicholl, Frank Stephan:
  On the Query Complexity of Sets. 206-217
  
• Viviana Bono, Michele Bugliesi, Luigi Liquori:
  A Lambda Calculus of Incomplete Objects. 218-229
  
• Michele Boreale, Luca Trevisan:
  Bisimilarity Problems Requiring Exponential Time. 230-241
  
• Arie de Bruin, Shan-Hwei Nienhuys-Cheng:
  Linear Dynamic Kahn Networks Are Deterministic. 242-254
  
• X. Cai, Ton Kloks, C. K. Wong:
  Shortest Path Problems with Time Constraints. 255-266
  
• Bogdan S. Chlebus, Artur Czumaj, Leszek Gasieniec, Miroslaw Kowaluk, Wojciech Plandowski:
  Parallel Alternating-Direction Access Machine. 267-278
  
• Flavio Corradini, Marco Pistore:
  Specification and Verification of Timed Lazy Systems. 279-290
  
• Stéphane Demri:
  A Class of Information Logics with a Decidable Validity Problem. 291-302
  
• Anders Dessmark, Andrzej Lingas:
  On the Power of Nonconservative PRAM. 303-311
  
• Bruno Durand:
  Self-Similarity Viewed as a Local Property via Tile Sets. 312-323
  
• Kai Engelhardt, Willem P. de Roever:
  Simulation of Specification Statements in Hoare Logic. 324-335
  
• Zoltán Ésik, Anna Labella:
  Equational Properties of Iteration in Algebraically Complete Categories. 336-347
  
• Henning Fernau:
  On Unconditional Transfer. 348-359
  
• Dimitris Fotakis, Paul G. Spirakis:
  (poly(log log n), poly(log log n))-Restricted Verifiers are Unlikely to Exist for Languages in NP. 360-371
  
• Leszek Gasieniec, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc:
  Minimizing Congestion of Layouts for ATM Networks with Faulty Links. 372-381
  
• Ian Glaister, Jeffrey Shallit:
  Polynomial Automaticity, Context-Free Languages, and Fixed Points of Morphism (Extended Abstract). 382-393
  
• Ursula Goltz, Heike Wehrheim:
  Causal Testing. 394-406
  
• Zhenjiang Hu, Hideya Iwasaki, Masato Takeichi:
  Construction of List Homomorphisms by Tupling and Fusion. 407-418
  
• Marta Z. Kwiatkowska, Gethin Norman:
  Probabilistic Metric Semantics for a Simple Language with Recursion. 419-430
  
• Andrea Maggiolo-Schettini, Józef Winkowski:
  Dynamic Graphs. 431-442
  
• Sabrina Mantaci, Antonio Restivo:
  Equations on Trees. 443-456
  
• Enno Ohlebusch, Esko Ukkonen:
  On the Equivalence Problem for E-Pattern Languages. 457-468
  
• Wieslaw Pawlowski, Pawel Paczkowski, Stefan Sokolowski:
  Specifying and Verifying Parametric Processes. 469-481
  
• Regimantas Pliuskevicius:
  On Saturation with Flexible Function Symbols. 482-493
  
• Carsten Rössner, Jean-Pierre Seifert:
  Approximating Good Simultaneous Diophantine Approximations Is Almost NP-Hard. 494-505
  
• Patrice Séébold:
  On the Conjugation of Standard Morphisms. 506-516
  
• Hui Shi:
  A Semantic Matching Algorithm: Analysis and Implementation. 517-528
  
• Jop F. Sibeyn:
  Routing on Triangles, Tori and Honeycombs. 529-541
  
• Pilar de la Torre, David T. Kao:
  A Uniform Analysis of Trie Structures that Store Prefixing-Keys with Application to Doubly-Chained Prefixing-Tries. 542-553
  
• Axel Wabenhorst:
  On Fairness in Terminating and Reactive Programs. 554-565
  
• Tomoyuki Yamakami:
  Polynomial Time Samplable Distributions. 566-578
  
• Elena Zucca:
  From Static to Dynamic Abstract Data-Types. 579-590