20. MFCS 1995: Prague, Czech Republic

Invited Papers

• Micah Adler, John W. Byers, Richard M. Karp:
  Scheduling Parallel Communication: The h-relation Problem. 1-20
  
• Stefan Arnborg:
  Decomposable Structures, Boolean Function Representations, and Optimization. 21-36
  
• Michele Flammini, Jan van Leeuwen, Alberto Marchetti-Spaccamela:
  The Complexity of Interval Routing on Random Graphs. 37-49
  
• Viliam Geffert:
  Bridging Across the log(n) Space Frontier. 50-65
  
• Georg Gottlob, Nicola Leone, Helmut Veith:
  Second Order Logic and the Weak Exponential Hierarchies. 66-81
  
• Juris Hartmanis:
  On the Computing Paradigm and Computational Complexity. 82-92
  
• Daniel J. Lehmann:
  Ranked Structures in Nonmonotonic Reasoning and Belief Revision: Abstract. 93
  
• Dominique Perrin:
  Symbolic Dynamics and Finite Automata. 94-104
  
• Alexander A. Razborov:
  Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract). 105
  
• Paul M. B. Vitányi:
  Physics and the New Computation. 106-128
  

Structural Complexity Theory

• Eric Allender, Martin Strauss:
  Measure on P: Robustness of the Notion. 129-138
  
• Hans-Jörg Burtschick:
  Comparing Counting Classes for Logspace, One-way Logspace, and First-order. 139-148
  
• Carsten Damm, Markus Holzer:
  Automata That Take Advice. 149-158
  
• Steven Homer, Sarah Mocas:
  Nonuniform Lower Bounds for Exponential Time Classes. 159-168
  
• Susanne Kaufmann, Martin Kummer:
  On a Quantitative Notion of Uniformity. 169-178
  
• Wolfgang Merkle, Yongge Wang:
  Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities. 179-190
  

Algorithms

• Danièle Beauquier, Dima Burago, Anatol Slissenko:
  On the Complexity of Finite Memory Policies for Markov Decision Processes. 191-200
  
• Thomas Hofmeister, Hanno Lefmann:
  Derandomization for Sparse Approximations and Independent Sets. 201-210
  
• Jyrki Katajainen, Tomi Pasanen, George Titan:
  Asymptotically Efficient In-Place Merging. 211-220
  

Complexity Theory

• Peter Heusch:
  The Complexity of the Falsifiability Problem for Pure Implicational Formulas. 221-226
  
• Viggo Kann:
  Strong Lower Bounds on the Approximability of some NPO PB-Complete Maximization Problems. 227-236
  
• Hanno Lefmann, Petr Savický:
  Some Typical Properties of Large AND/OR Boolean Formulas. 237-246
  

Graph Models of Computations

• Martin Hühne:
  The Hedge: An Efficient Storage Device for Turing Machines with One Head (Extended Abstract). 247-256
  
• Osamu Maruyama, Satoru Miyano:
  Graph Inference from a Walk for TRees of Bounded Degree 3 is NP-Complete. 257-266
  
• Ivan Stojmenovic:
  Honecomb Networks. 267-276
  
• Sophie Fischer, Lane A. Hemaspaandra, Leen Torenvliet: Witness-Isomorphic Reductions and the Local Search Problem (Extended Abstract). 277-287 , full version: http: //www.cs.rochester.edu/trs/theory-trs.html as 94.tr.522

Lower Bounds

• Claudia Bertram-Kretzberg, Thomas Hofmeister:
  Multiple Product Modulo Arbitrary Numbers. 288-298
  
• Christoph Meinel, Stephan Waack:
  Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems. 299-308
  
• Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini:
  Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages. 309-318
  
• Stanislav Zák:
  A Superpolynomial Lower Bound for (1, +k(n))-Branching Programs. 319-325
  

Formal Languages

• Luca Breveglieri, Alessandra Cherubini, Stefano Crespi-Reghizzi:
  Deterministic Parsing for Augmented Context-free Grammars. 326-336
  
• Filippo Mignosi, Antonio Restivo, Sergio Salemi:
  A Periodicity Theorem on Words and Applications. 337-348
  
• Günter Hotz, Gisela Pitsch:
  A New Approach to Analyse Coupled-Context-Free Languages. 349-358
  

Unification, Rewriting, Type Theory

• Miki Hermann, Phokion G. Kolaitis:
  Computational Complexity of Simultaneous Elementary Matching Problems (Extended Abstract). 359-370
  
• M. R. K. Krishna Rao:
  Graph Reducibility of Term Rewriting Systems. 371-381
  
• Pawel Urzyczyn:
  Positive Recursive Type Assignment. 382-391
  

Distributed Computation

• Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio:
  String Recognition on Anonymous Rings. 392-401
  
• Zsuzsanna Róka:
  The Firing Squad Synchronization Problem on Cayley Graphs. 402-411
  
• Jop F. Sibeyn, Michael Kaufmann:
  Solving Cheap Graph Problems an Meshes. 412-422
  

Concurrency

• Olaf Burkart, Didier Caucal, Bernhard Steffen:
  An Elementary Bisimulation Decision Procedure for Arbitrary Context-Free Processes. 423-433
  
• Serge Bauget, Paul Gastin:
  On Congruences and Partial Orders. 434-443
  
• Flavio Corradini, Roberto Gorrieri, Marco Roccetti:
  Performance Preorder: Ordering Processes with Respect to Speed. 444-453
  
• William Ferreira, Matthew Hennessy:
  Towards a Semantic Theory of CML (Extended Abstract). 454-466
  
• Sébastien Huguet, Antoine Petit:
  Modular Constructions of Distributing Automata. 467-478
  
• Davide Sangiorgi:
  On the Proof Method for Bisimulation (Extended Abstract). 479-488
  

Semantics

• Clare E. Martin:
  Towards a Calculus of Predicate Transformers. 489-498
  
• Martín Abadi, Stephan Merz:
  An Abstract Account of Composition. 499-508
  
• Roel van der Goot, Arie de Bruin:
  Syntax and Semantics of Procol. 509-518
  

Model Checking

• Jens Chr. Godskesen, Kim Guldstrand Larsen:
  Synthesizing Distinguishing Formulae for Real Time Systems (Extended Abstract). 519-528
  
• François Laroussinie, Kim Guldstrand Larsen, Carsten Weise:
  From Timed Automata to Logic - and Back. 529-539
  
• Johann A. Makowsky, Elena V. Ravve:
  Incremental Model Checking for Decomposable Structures (Extended Abstract). 540-551
  

Formal Calculi

• David Janin, Igor Walukiewicz:
  Automata for the Modal mu-Calculus and related Results. 552-562
  
• Peter Niebert:
  A v-Calculus with Local Views for Systems of Sequential Agents. 563-573
  
• R. Feinsilver, René Schott:
  An Operator Calculus Approach to the Evolution of Dynamic Data Structures. 574-586