24. ICALP 1997: Bologna, Italy

Pierpaolo Degano, Roberto Gorrieri, Alberto Marchetti-Spaccamela (Eds.): Automata, Languages and Programming, 24th International Colloquium, ICALP'97, Bologna, Italy, 7-11 July 1997, Proceedings. Lecture Notes in Computer Science 1256 Springer 1997, ISBN 3-540-63165-8 BibTeX

@proceedings{DBLP:conf/icalp/1997,
  editor    = {Pierpaolo Degano and
               Roberto Gorrieri and
               Alberto Marchetti-Spaccamela},
  title     = {Automata, Languages and Programming, 24th International Colloquium,
               ICALP'97, Bologna, Italy, 7-11 July 1997, Proceedings},
  booktitle = {ICALP},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1256},
  year      = {1997},
  isbn      = {3-540-63165-8},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Papers

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

Formal Languages I

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

Computability

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

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 BibTeX
Harry Buhrman, Stephen A. Fenner, Lance Fortnow: Results on Resource-Bounded Measure. 188-194 BibTeX
Farid M. Ablayev: Randomization and Nondeterminism Are Comparable for Ordered Read-Once Branching Programs. 195-202 BibTeX
Bruno Codenotti, Funda Ergün, Peter Gemmell, Ravi Kumar: Checking Properties of Polynomials (Extended Abstract). 203-213 BibTeX
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 BibTeX

Semantics I

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

Algorithms I

Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup: Minimizing Diameters of Dynamic Trees. 270-280 BibTeX
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 BibTeX
Torben Hagerup: Dynamic Algorithms for Graphs of Bounded Treewidth. 292-302 BibTeX

Calculi for Concurrency I

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

Formal Languages II

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

Calculi for Concurrency II

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

Algorithms II

Uwe Schwiegelshohn, Lothar Thiele: Periodic and Non-periodic Min-Max Equations. 379-389 BibTeX
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 BibTeX
Andris Ambainis: Upper Bound on Communication Complexity of Private Information Retrieval. 401-407 BibTeX

Logic and Verification

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

Analysis of Algorithms

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

Process Equivalences

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

Routing Algorithms

Christos Kaklamanis, Pino Persiano, Thomas Erlebach, Klaus Jansen: Constrained Bipartite Edge Coloring with Applications to Wavelength Routing. 493-504 BibTeX
Luisa Gargano, Pavol Hell, Stephane Perennes: Colouring Paths in Directed Symmetric Trees with Applications to WDM Routing. 505-515 BibTeX
Yair Bartal, Stefano Leonardi: On-Line Routing in All-Optical Networks. 516-526 BibTeX
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 BibTeX

Petri Nets and Process Theory

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

Algorithms III

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

Rewriting

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

Formal Languages III

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

Cryptography

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

Algorithms IV

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

Semantics II and Automata

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

Biocomputing

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

Logic Programming

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