23. ICALP 1996: Paderborn, Germany

Friedhelm Meyer auf der Heide, Burkhard Monien (Eds.): Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 8-12 July 1996, Proceedings. Lecture Notes in Computer Science 1099 Springer 1996, ISBN 3-540-61440-0 BibTeX

@proceedings{DBLP:conf/icalp/1996,
  editor    = {Friedhelm Meyer auf der Heide and
               Burkhard Monien},
  title     = {Automata, Languages and Programming, 23rd International Colloquium,
               ICALP96, Paderborn, Germany, 8-12 July 1996, Proceedings},
  booktitle = {ICALP},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1099},
  year      = {1996},
  isbn      = {3-540-61440-0},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Papers

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

Process Theory I

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

Fairness, Domination, and the µ-Calculus

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

Logic and Algebra

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

Languages and Processes

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

Algebraic Complexity

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

Graph Algorithms

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

Automata

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

Complexity Theory

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

Combinatorics on Words

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

Algorithms I

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

Lower Bounds

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

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 BibTeX
Petr Jancar, Javier Esparza: Deciding Finiteness of Petri Nets Up To Bisimulation. 478-489 BibTeX
Chiara Bodei, Pierpaolo Degano, Corrado Priami: Mobile Processes with a Distributed Environment. 490-501 BibTeX
Rob J. van Glabbeek: The Meaning of Negative Premises in Transition System Specifications II. 502-513 BibTeX

Data Structures

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

Parallel Algorithms

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

Distributed Systems

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

Algorithms II

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