23. ICALP 1996: Paderborn, Germany

Invited Papers

• Harald Ganzinger:
  Saturation-Based Theorem Proving (Abstract). 1-3
  
• Abhiram G. Ranade:
  Bandwidth Efficient Parallel Computation. 4-23
  
• Véronique Bruyère, Michel Latteux:
  Variable-Length Maximal Codes. 24-47
  
• Alexander A. Razborov:
  Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic. 48-62
  

Process Theory I

• Xiao Jun Chen, Rocco De Nicola:
  Algebraic Characterizations of Decorated Trace Equivalences over Tree-Like Structures. 63-74
  
• Lars Jenner, Walter Vogler:
  Fast Asynchronous Systems in Dense Time. 75-86
  

Fairness, Domination, and the µ-Calculus

• Giacomo Lenzi:
  A Hierarchy Theorem for the µ-Calculus. 87-97
  
• Julian C. Bradfield, Javier Esparza, Angelika Mader:
  An Effective Tableau System for the Linear Time µ-Calculus. 98-109
  
• Yuh-Jzer Joung:
  Characterizing Fairness Implementability for Multiparty Interaction. 110-121
  
• Salvador Lucas:
  Termination of Context-Sensitive Rewriting by Rewriting. 122-133
  

Logic and Algebra

• Allan Cheng, Dexter Kozen:
  A Complete Gentzen-Style Axiomatization for Set Constraints. 134-145
  
• Michel Billaud:
  Fatal Errors in Conditional Expressions (Extended Abstract). 146-157
  
• Till Mossakowski:
  Different Types of Arrow Between Logical Frameworks. 158-169
  
• John C. Mitchell, Ramesh Viswanathan:
  Effective Models of Polymorphism, Subtyping and Recursion (Extended Abstract). 170-181
  

Languages and Processes

• D. J. B. Bosscher, W. O. David Griffioen:
  Regularity for a Large Class of Context-Free Processes is Decidable. 182-193
  
• Didier Caucal:
  On Infinite Transition Graphs Having a Decidable Monadic Theory. 194-205
  
• Géraud Sénizergues:
  Semi-Groups Acting on Context-Free Graphs. 206-218
  
• Leonid P. Lisovik:
  Hard Sets Method and Semilinear Reservoir Method with Applications. 219-231
  

Algebraic Complexity

• Philippe Flajolet, Xavier Gourdon, Daniel Panario:
  Random Polynomials and Polynomial Factorization. 232-243
  
• Ulla Koppenhagen, Ernst W. Mayr:
  Optimal Gröbner Base Algorithms for Binomial Ideals. 244-255
  

Graph Algorithms

• Ton Kloks, Dieter Kratsch, C. K. Wong:
  Minimum Fill-In on Circle and Circular-Arc Graphs. 256-267
  
• Zhi-Zhong Chen:
  Practical Approximation Schemes for Maximum Induced-Subgraph Problems on K_{3, 3}-free or K_5-free Graphs. 268-279
  
• Elias Koutsoupias, Christos H. Papadimitriou, Mihalis Yannakakis:
  Searching a Fixed Graph. 280-289
  
• Monika Rauch Henzinger, Mikkel Thorup:
  Improved Sampling with Applications to Dynamic Graph Algorithms. 290-299
  

Automata

• Jean-Eric Pin:
  The Expressive Power of Existential First Order Sentences of Büchi's Sequential Calculus. 300-311
  
• Roope Kaivola:
  Fixpoints for Rabin Tree Automata Make Complementation Easy. 312-323
  
• Kosaburo Hashiguchi:
  New Upper Bounds to the Limitedness of Distance Automata. 324-335
  
• Pascal Raymond:
  Recognizing Regular Expressions by Means of Dataflow Networks. 336-347
  

Complexity Theory

• Farid M. Ablayev, Marek Karpinski:
  On the Power of Randomized Branching Programs. 348-356
  
• Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim:
  Hitting Sets Derandomize BPP. 357-368
  
• Ronald V. Book, Heribert Vollmer, Klaus W. Wagner:
  On Type-2 Probabilistic Quantifiers. 369-380
  
• Jirí Wiedermann:
  Speeding-up Single-Tape Nondeterministic Computations by Single Alternation, with Separation Results. 381-392
  

Combinatorics on Words

• Sandrine Julia:
  On \omega-Generators and Codes. 393-402
  
• Aldo de Luca:
  On Standard Sturmian Morphisms. 403-415
  

Algorithms I

• Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis, Douglas R. Stinson:
  Constructions and Bounds for Visual Cryptography. 416-428
  
• Yossi Azar, Yair Bartal, Esteban Feuerstein, Amos Fiat, Stefano Leonardi, Adi Rosén:
  On Capital Investment. 429-441
  

Lower Bounds

• Peter Bro Miltersen:
  Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication. 442-453
  
• Phillip G. Bradford, Knut Reinert:
  Lower Bounds for Row Minima Searching (Extended Abstract). 454-465
  

Process Theory II

• Sandeep K. Shukla, Harry B. Hunt III, Daniel J. Rosenkrantz, Richard Edwin Stearns:
  On the Complexity of Relational Problems for Finite State Processes (Extended Abstract). 466-477
  
• Petr Jancar, Javier Esparza:
  Deciding Finiteness of Petri Nets Up To Bisimulation. 478-489
  
• Chiara Bodei, Pierpaolo Degano, Corrado Priami:
  Mobile Processes with a Distributed Environment. 490-501
  
• Rob J. van Glabbeek:
  The Meaning of Negative Premises in Transition System Specifications II. 502-513
  

Data Structures

• Susanne Albers, Michael Mitzenmacher:
  Average Case Analyses of List Update Algorithms, with Applications to Data Compression. 514-525
  
• Frank Schulz, Elmar Schömer:
  Self-Organizing Data Structures with Dependent Accesses. 526-537
  
• Vicky Siu-Ngan Choi, Mordecai J. Golin:
  Lopsided Trees: Analyses, Algorithms, and Applications. 538-549
  
• Martin Farach, S. Muthukrishnan:
  Optimal Logarithmic Time Randomized Suffix Tree Construction. 550-561
  

Parallel Algorithms

• Noga Alon, Aravind Srinivasan:
  Improved Parallel Approximation of a Class of Integer Programming Programming Problems. 562-573
  
• Jean-Claude Bermond, Luisa Gargano, Stephane Perennes, Adele A. Rescigno, Ugo Vaccaro:
  Efficient Collective Communication in Optical Networks. 574-585
  
• Bogdan S. Chlebus, Anna Gambin, Piotr Indyk:
  Shared-Memory Simulations on a Faulty-Memory DMM. 586-597
  
• Kieran T. Herley, Andrea Pietracaprina, Geppino Pucci:
  Fast Deterministic Backtrack Search. 598-609
  

Distributed Systems

• Xiangdong Yu, Moti Yung:
  Agent Rendezvous: A Dynamic Symmetry-Breaking Problem. 610-621
  
• Yonatan Aumann, Michael A. Bender:
  Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler. 622-633
  

Algorithms II

• Lenore Cowen, Joan Feigenbaum, Sampath Kannan:
  A Formal Framework for Evaluating Heuristic Programs. 634-645
  
• Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, Joel Wein:
  Improved Scheduling Algorithms for Minsum Criteria. 646-657
  
• Mike Paterson, Teresa M. Przytycka:
  On the Complexity of String Folding. 658-669
  
• David Fernández-Baca, Jens Lagergren:
  A Polynomial-Time Algorithm for Near-Perfect Phylogeny. 670-680