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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Last update Mon May 20 23:11:06 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page