21. ICALP 1994: Jerusalem, Israel

Theory of Computation

• Pavel Pudlák:
  Unexpected Upper Bounds on the Complexity of Some Communication Games. 1-10
  
• Henning Fernau, Ludwig Staiger:
  Valuations and Unambiguity of Languages, with Applications to Fractal Geometry. 11-22
  
• Hava T. Siegelmann:
  On The Computational Power of Probabilistic and Faulty Neural Networks. 23-34
  

Automata, Computation Models

• Karlis Cerans:
  Deciding Properties of Integral Relational Automata. 35-46
  
• Yonatan Aumann, Judit Bar-Ilan, Uriel Feige:
  On the Cost of Recomputing: Tight Bounds on Pebbling with Faults. 47-58
  
• Eugene Asarin, Oded Maler:
  On some Relations between Dynamical Systems and Transition Systems. 59-72
  
• Noa Globerman, David Harel:
  Complexity Results for Multi-Pebble Automata and their Logics. 73-82
  

Expressive Power

• Paris C. Kanellakis, Gerd G. Hillebrand, Harry G. Mairson:
  An Analysis of the Core-ML Language: Expressive Power and Type Reconstruction. 83-105
  
• Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht:
  Expressiveness of Efficient Semi-Deterministic Choice Constructs. 106-117
  
• Erich Grädel, Yuri Gurevich:
  Tailoring Recursing for Complexity. 118-129
  

Automata, Concurrency

• Nils Klarlund, Madhavan Mukund, Milind A. Sohoni:
  Determinizing Asynchronous Automata. 130-141
  
• Anca Muscholl:
  On the Complementation of Büchi Asynchronous Cellular Automata. 142-153
  
• Flavio Corradini, Rocco De Nicola:
  Distribution and Locality of Concurrent Systems. 154-165
  
• Rainer Gawlick, Roberto Segala, Jørgen F. Søgaard-Andersen, Nancy A. Lynch:
  Liveness in Timed and Untimed Systems. 166-177
  

Pattern Matching

• José-Ramón Sánchez-Couso, María-Inés Fernández-Camacho:
  Average-Case Analysis of Pattern-Matching in Trees under the BST Probability Model. 178-190
  
• Tao Jiang, Ming Li:
  On the Approximation of Shortest Common Supersequences and Longest Common Subsequences. 191-202
  
• Ramesh Hariharan, S. Muthukrishnan:
  Optimal Parallel Algorithms for Prefix Matching. 203-214
  
• Amihood Amir, Gary Benson, Martin Farach:
  Optimal Two-Dimensional Compressed Matching. 215-226
  

Data Structures

• Giuseppe F. Italiano, Rajiv Ramaswami:
  Maintaining Spanning Trees of Small Diameter. 227-238
  
• Joseph Gil, Yossi Matias:
  Simple Fast Parallel Hashing. 239-250
  
• Teresa M. Przytycka, Lawrence L. Larmore:
  The Optimal Alphabetic Tree Problem Revisited. 251-262
  

Computation Complexity

• Harry Buhrman, Leen Torenvliet:
  On the Cutting Edge of Relativization: The Resource Bounded Injury Method. 263-273
  
• Jean-Camille Birget, Stuart W. Margolis, John C. Meakin, Pascal Weil:
  PSPACE-Completeness of Certain Algorithmic Problems on the Subgroups of Free Groups. 274-285
  

Semantics, Logic and Verification I

• Matthew Hennessy:
  Higher-Order Process and Their Models. 286-303
  
• Bart Vergauwen, Johan Lewi:
  Efficient Local Correctness Checking for Single and Alternating Boolean Equation Systems. 304-315
  
• Parosh Aziz Abdulla, Bengt Jonsson:
  Undecidable Verification Problems for Programs with Unreliable Channels. 316-327
  
• Limor Fix, Fred B. Schneider:
  Reasoning about Programs by Exploiting the Environment. 328-339
  

Semantics, Logic and Verification II

• Torben Braüner:
  A Model of Intuitionistic Affine Logic From Stable Domain Theory. 340-351
  
• Gordon D. Plotkin, Glynn Winskel:
  Bistructures, Bidomains and Linear Logic. 352-363
  
• Adnan Aziz, Vigyan Singhal, Felice Balarin, Robert K. Brayton, Alberto L. Sangiovanni-Vincentelli:
  Equivalences for Fair Kripke Structures. 364-375
  
• Franck van Breugel:
  Generalized Finiteness Conditions of Labelled Transition Systems. 376-387
  

Formal Languages

• Manfred Droste:
  A KLeene Theorem for Recognizable Languages over Concurrency Monoids. 388-399
  
• Helmut Seidl:
  Least Solutions of Equations over N. 400-411
  
• Günter Hotz, Gisela Pitsch:
  Fast Uniform Analysis of Coupled-Context-Free Languages. 412-423
  
• Jean-Eric Pin:
  Polynomial Closure of Group Languages and Open Sets of the Hall Topology. 424-435
  

Term Rewriting Systems

• Anne-Cécile Caron, Hubert Comon, Jean-Luc Coquidé, Max Dauchet, Florent Jacquemard:
  Pumping, Cleaning and Symbolic Constraints Solving. 436-449
  
• Claus Hintermeier, Claude Kirchner, Hélène Kirchner:
  Dynamically-Typed Computations for Order-Sorted Equational Presentations. 450-461
  
• Roberto Di Cosmo, Delia Kesner:
  Combining First Order Algebraic Rewriting Systems, Recursion and Extensional Lambda Calculi. 462-472
  

Algorithms and Communications

• Eli Upfal:
  On the Theory of Interconnection Networks for Parallel Computers. 473-486
  
• Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis:
  Multiway Cuts in Directed and Node Weighted Graphs. 487-498
  
• Uriel Feige:
  A Fast Randomized LOGSPACE Algorithm for Graph Connectivity. 499-507
  
• Sotiris E. Nikoletseas, Krishna V. Palem, Paul G. Spirakis, Moti Yung:
  Short Vertex Disjoint Paths and Multiconnectivity in Random Graphs: Reliable Network Computing. 508-519
  

Graph Algorithms

• Jens Lagergren:
  The Size of an Interwine. 520-531
  
• Raphael Yuster, Uri Zwick:
  Finding Even Cycles Even Faster. 532-543
  
• Franz Höfting, Egon Wanke:
  Polynomial Time Analysis of Torodial Periodic Graphs. 544-555
  
• Paola Bonizzoni:
  A Tight Lower Bound for Primitivity in k-Structures. 556-567
  

Randomized Complexity

• Carlo Blundo, Alfredo De Santis, Ugo Vaccaro:
  Randomness in Distributed Protocols. 568-579
  
• Rusins Freivalds, Marek Karpinski:
  Lower Space Bounds for Randomized Computation. 580-592
  
• Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer, Stephan Weis:
  The Average Case Complexity of the Parallel Prefix Problem. 593-604
  

Various Algorithms

• Mordecai J. Golin, Neal E. Young:
  Prefix Codes: Equiprobable Words, Unequal Letter Costs. 605-617
  
• C. Greg Plaxton, Torsten Suel:
  A Super-Logarithmic Lower Bound for Hypercubic Sorting Networks. 618-629
  
• Aohan Mei, Yoshihide Igarashi:
  Efficient Strategies for Robot Navigation in Unknown Environment. 630-641