24. ICALP 1997: Bologna, Italy

Invited Papers

• Robin Milner:
  Graphical Calculi for Interaction (Abstract). 1
  
• Christos H. Papadimitriou:
  NP-Completeness: A Retrospective. 2-6
  
• Kurt Mehlhorn, Stefan Näher, Christian Uhrig:
  The LEDA Platform of Combinatorial and Geometric Computing. 7-16
  
• Olivier Carton, Dominique Perrin:
  The Wadge-Wagner Hierarchy of omega-Rational Sets. 17-35
  
• Krzysztof R. Apt:
  From Chaotic Iteration to Constraint Propagation. 36-55
  
• Laura F. Landweber, Richard J. Lipton:
  DNA²DNA Computations: A Potential "Killer App"? 56-64
  

Formal Languages I

• Bruno Durand:
  Tilings and Quasiperiodicity. 65-75
  
• Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin:
  Enumerative Sequences of Leaves in Rational Trees. 76-86
  
• Véronique Bruyère:
  A Completion Algorithm for Codes with Bounded Synchronization Delay. 87-97
  
• Juhani Karhumäki, Wojciech Plandowski, Filippo Mignosi:
  The Expressibility of Languages and Relations by Word Equations. 98-109
  
• Martin Beaudry, François Lemieux, Denis Thérien:
  Finite Loops Recognize Exactly the Regular Open Languages. 110-120
  

Computability

• Pietro Di Gianantonio:
  An Abstract Data Type for Real Numbers. 121-131
  
• James I. Lathrop, Jack H. Lutz:
  Recursive Computational Depth. 132-142
  
• Olivier Bournez:
  Some Bounds on the Computational Power of Piecewise Constant Derivative Systems (Extended Abstract). 143-153
  
• Yuri Gurevich, Andrei Voronkov:
  Monadic Simultaneous Rigid E-Unification and Related Problems. 154-165
  
• Klaus Weihrauch:
  Computability on the Probability Measures on the Borel Sets of the Unit Interval. 166-176
  

Computational Complexity

• Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
  Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-Offs. 177-187
  
• Harry Buhrman, Stephen A. Fenner, Lance Fortnow:
  Results on Resource-Bounded Measure. 188-194
  
• Farid M. Ablayev:
  Randomization and Nondeterminism Are Comparable for Ordered Read-Once Branching Programs. 195-202
  
• Bruno Codenotti, Funda Ergün, Peter Gemmell, Ravi Kumar:
  Checking Properties of Polynomials (Extended Abstract). 203-213
  
• Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe:
  Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP. 214-224
  

Semantics I

• Kohei Honda, Nobuko Yoshida:
  Game Theoretic Analysis of Call-by-Value Computation. 225-236
  
• Roberto Di Cosmo, Neil Ghani:
  On Modular Properties of Higher Order Extensional Lambda Calculi. 237-247
  
• Eike Ritter, Valeria de Paiva:
  On Explicit Substitution and Names (Extended Abstract). 248-258
  
• Andrea Asperti, Cosimo Laneve:
  On the Dynamics of Sharing Graphs. 259-269
  

Algorithms I

• Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup:
  Minimizing Diameters of Dynamic Trees. 270-280
  
• Sven Oliver Krumke, Madhav V. Marathe, Hartmut Noltemeier, R. Ravi, S. S. Ravi, Ravi Sundaram, Hans-Christoph Wirth:
  Improving Spanning Trees by Upgrading Nodes. 281-291
  
• Torben Hagerup:
  Dynamic Algorithms for Graphs of Bounded Treewidth. 292-302
  

Calculi for Concurrency I

• Davide Sangiorgi:
  The Name Discipline of Uniform Receptiveness (Extended Abstract). 303-313
  
• Anna Philippou, David Walker:
  On Confluence in the pi-Calculus. 314-324
  
• Yuxi Fu:
  A Proof Theoretical Approach to Communication. 325-335
  

Formal Languages II

• Volker Diekert, Yuri Matiyasevich, Anca Muscholl:
  Solving Trace Equations Using Lexicographical Normal Forms. 336-346
  
• Thomas Wilke:
  Star-Free Picture Expressions are Strictly Weaker Than First-Order Logic. 347-357
  

Calculi for Concurrency II

• Marco Bernardo:
  An Algebra-Based Method to Associate Rewards with EMPA Terms. 358-368
  
• Ian A. Mason, Carolyn L. Talcott:
  A Semantically Sound Actor Tranlsation. 369-378
  

Algorithms II

• Uwe Schwiegelshohn, Lothar Thiele:
  Periodic and Non-periodic Min-Max Equations. 379-389
  
• Edson Cáceres, Frank K. H. A. Dehne, Afonso Ferreira, Paola Flocchini, Ingo Rieping, Alessandro Roncato, Nicola Santoro, Siang W. Song:
  Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP. 390-400
  
• Andris Ambainis:
  Upper Bound on Communication Complexity of Private Information Retrieval. 401-407
  

Logic and Verification

• David Harel, Eli Singerman:
  Computation Paths Logic: An Expressive, yet Elementary, Process Logic (abridged version). 408-418
  
• Olaf Burkart, Bernhard Steffen:
  Model Checking the Full Modal Mu-Calculus for Infinite Sequential Processes. 419-429
  
• Christel Baier, Edmund M. Clarke, Vassili Hartonas-Garmhausen, Marta Z. Kwiatkowska, Mark Ryan:
  Symbolic Model Checking for Probabilistic Processes. 430-440
  

Analysis of Algorithms

• John Michael Robson:
  On the Concentration of the Height of Binary Search Trees. 441-448
  
• Salvador Roura:
  An Improved Master Theorem for Divide-and-Conquer Recurrences. 449-459
  

Process Equivalences

• Erik P. de Vink, Jan J. M. M. Rutten:
  Bisimulation for Probabilistic Transition Systems: A Coalgebraic Approach. 460-470
  
• James Riely, Matthew Hennessy:
  Distributed Processes and Location Failures (Extended Abstract). 471-481
  
• Michele Boreale, Rocco De Nicola, Rosario Pugliese:
  Basic Observables for Processes. 482-492
  

Routing Algorithms

• Christos Kaklamanis, Pino Persiano, Thomas Erlebach, Klaus Jansen:
  Constrained Bipartite Edge Coloring with Applications to Wavelength Routing. 493-504
  
• Luisa Gargano, Pavol Hell, Stephane Perennes:
  Colouring Paths in Directed Symmetric Trees with Applications to WDM Routing. 505-515
  
• Yair Bartal, Stefano Leonardi:
  On-Line Routing in All-Optical Networks. 516-526
  
• Tamar Eilam, Michele Flammini, Shmuel Zaks:
  A Complete Characterization of the Path Layout Construction Problem for ATM Networks with Given Hop Count and Load (Extended Abstract). 527-537
  

Petri Nets and Process Theory

• Walter Vogler:
  Efficiency of Asynchronous Systems and Read Arcs in Petri Nets. 538-548
  
• Petr Jancar:
  Bisimulation Equivalence is Decidable for One-Counter Processes. 549-559
  
• Ahmed Bouajjani, Peter Habermehl:
  Symbolic Reachability Analysis of FIFO Channel Systems with Nonregular Sets of Configurations (Extended Abstract). 560-570
  
• Wan Fokkink:
  Axiomatizations for the Perpetual Loop in Process Algebra. 571-581
  
• Thomas A. Henzinger, Peter W. Kopke:
  Discrete-Time Control for Rectangular Hybrid Automata. 582-593
  

Algorithms III

• Monika Rauch Henzinger, Valerie King:
  Maintaining Minimum Spanning Trees in Dynamic Graphs. 594-604
  
• Roberto Grossi, Giuseppe F. Italiano:
  Efficient Splitting and Merging Algorithms for Order Decomposable Problems (Extended Abstract). 605-615
  
• Sanjeev Khanna, S. Muthukrishnan, Steven Skiena:
  Efficient Array Partitioning. 616-626
  
• Hans L. Bodlaender, Dimitrios M. Thilikos:
  Constructive Linear Time Algorithms for Branchwidth. 627-637
  

Rewriting

• Paliath Narendran, Friedrich Otto:
  The Word Matching Problem Is Undecidable For Finite Special String-Rewriting Systems That Are Confluent. 638-648
  
• Zurab Khasidashvili, John R. W. Glauert:
  The Geometry of Orthogonal Reduction Spaces. 649-659
  
• Massimo Marchiori:
  The Theory of Vaccines. 660-670
  

Formal Languages III

• Géraud Sénizergues:
  The Equivalence Problem for Deterministic Pushdown Automata is Decidable. 671-681
  
• Manfred Droste, Paul Gastin:
  On Recognizable and Rational Formal Power Series in Partially Commuting Variables. 682-692
  
• Julien Cassaigne:
  On a Conjecture of J. Shallit. 693-704
  

Cryptography

• Yair Frankel, Moti Yung:
  On Characterization of Escrow Encryption Schemes. 705-715
  
• Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano:
  Randomness-Efficient Non-Interactive Zero-Knowledge (Extended Abstract). 716-726
  

Algorithms IV

• Klaus Jansen:
  Approximation Results for the Optimum Cost Partition Problem. 727-737
  
• Amotz Bar-Noy, Guy Kortsarz:
  The Minimum Color Sum of Bipartite Graphs. 738-748
  
• Toshihiro Fujito:
  A Primal-Dual Approach to Approximation of Node-Deletion Problems for Matroidal Properties. 749-759
  
• Hajo Broersma, Ton Kloks, Dieter Kratsch, Haiko Müller:
  Independent Sets in Asteroidal Triple-Free Graphs. 760-770
  

Semantics II and Automata

• Roberto Giacobazzi, Francesco Ranzato:
  Refining and Compressing Abstract Domains. 771-781
  
• Laurent Dami:
  Labelled Reductions, Runtime Errors and Operational Subsumption. 782-793
  
• Giovanni Manzini, Luciano Margara:
  A Complete and Efficiently Computable Topological Classification of D-dimensional Linear Cellular Automata over Z_m. 794-804
  
• Valentine Kabanets:
  Recognizability Equals Definability for Partial k-Paths. 805-815
  

Biocomputing

• Richard Beigel, Bin Fu:
  Molecular Computing, Bounded Nondeterminism, and Efficient Recursion. 816-826
  
• Péter L. Erdös, Mike A. Steel, László A. Székely, Tandy Warnow:
  Constructing Big Trees from Short Sequences. 827-837
  

Logic Programming

• Salvatore Ruggieri:
  Termination of Constraint Logic Programs. 838-848
  
• Francesco Buccafurri, Sergio Greco, Domenico Saccà:
  The Expressive Power of Unique Total Stable Model Semantics. 849-859