26. ICALP 1999: Prague, Czech Republic

@proceedings{DBLP:conf/icalp/99,
  editor    = {Jir\'{\i} Wiedermann and
               Peter van Emde Boas and
               Mogens Nielsen},
  title     = {Automata, Languages and Programming, 26th International Colloquium,
               ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1644},
  year      = {1999},
  isbn      = {3-540-66224-3},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Talks

• Miklós Ajtai:
  Generating Hard Instances of the Short Basis Problem. 1-9
  
• Luca Cardelli:
  Wide Area Computation. 10-24
  
• Kevin J. Compton, Scott Dexter:
  Proof Techniques for Cryptographic Protocols. 25-39
  
• Karl Crary, J. Gregory Morrisett:
  Type Structure for Low-Level Programming Languages. 40-54
  
• Felipe Cucker:
  Real Computations with Fake Numbers. 55-73
  
• N. G. de Bruijn:
  A Model for Associative Memory, a Basis for Thinking and Consciousness. 74-89
  
• Abbas Edalat, Marko Krznaric:
  Numerical Integration with Exact Real Arithmetic. 90-104
  
• Juris Hartmanis:
  Observations about the Nature and State of Computer Science (Keynote Address). 105
  
• Grzegorz Rozenberg, Arto Salomaa:
  DNA Computing: New Ideas and Paradigms. 106-118
  
• Jeffrey Scott Vitter:
  Online Data Structures in External Memory. 119-133
  
• Osamu Watanabe:
  From Computational Learning Theory to Discovery Science. 134-148
  

Contributed Papers

• Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh:
  Bounded Depth Arithmetic Circuits: Counting and Closure. 149-158
  
• Rajeev Alur, Kousha Etessami, Salvatore La Torre, Doron Peled:
  Parametric Temporal Logic for "Model Measuring". 159-168
  
• Rajeev Alur, Sampath Kannan, Mihalis Yannakakis:
  Communicating Hierarchical State Machines. 169-178
  
• Alexander E. Andreev, Juri L. Baskakov, Andrea E. F. Clementi, José D. P. Rolim:
  Small Pseudo-Random Sets Yield Hard Functions: New Tight Explict Lower Bounds for Branching Programs. 179-189
  
• Marek A. Bednarczyk, Andrzej M. Borzyszkowski:
  General Morphisms of Petri Nets (Extended Abstract). 190-199
  
• Piotr Berman, Marek Karpinski:
  On Some Tighter Inapproximability Results (Extended Abstract). 200-209
  
• Patricia Bouyer, Antoine Petit:
  Decomposition and Composition of Timed Automata. 210-219
  
• Harry Buhrman, Tao Jiang, Ming Li, Paul M. B. Vitányi:
  New Applications of the Incompressibility Method. 220-229
  
• Luca Cardelli, Andrew D. Gordon, Giorgio Ghelli:
  Mobility Types for Mobile Ambients. 230-239
  
• Peter Clote:
  Protein Folding, the Levinthal Paradox and Rapidly Mixing Markov Chains. 240-249
  
• Véronique Cortier, Harald Ganzinger, Florent Jacquemard, Margus Veanes:
  Decidable Fragments of Simultaneous Rigid Reachability. 250-260
  
• Maxime Crochemore, Filippo Mignosi, Antonio Restivo, Sergio Salemi:
  Text Compression Using Antidictionaries. 261-270
  
• Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano:
  Non-Interactive Zero-Knowledge: A Low-Randomness Characterization of NP. 271-280
  
• Martin Dickhöfer, Thomas Wilke:
  Timed Alternating Tree Automata: The Automata-Theoretic Solution to the TCTL Model Checking Problem. 281-290
  
• Yevgeniy Dodis, Sanjeev Khanna:
  Space Time Tradeoffs for Graph Properties. 291-300
  
• Catherine Dufourd, Petr Jancar, Ph. Schnoebelen:
  Boundedness of Reset P/T Nets. 301-310
  
• Joost Engelfriet, Hendrik Jan Hoogeboom:
  Two-Way Finite State Transducers and Monadic Second-Order Logic. 311-320
  
• Sergio Flesca, Sergio Greco:
  Partially Ordered Regular Languages for Graph Queries. 321-330
  
• Markus Frick, Martin Grohe:
  Deciding First-Order Properties of Locally Tree-Decomposalbe Graphs. 331-340
  
• Vashti Galpin:
  Comparison of Process Algebra Equivalences Using Formats. 341-350
  
• Cyril Gavoille, Nicolas Hanusse:
  Compact Routing Tables for Graphs of Bounded Genus. 351-360
  
• Georg Gottlob, Nicola Leone, Francesco Scarcello:
  Computing LOGCFL Certificates. 361-371
  
• Roberto Grossi, Giuseppe F. Italiano:
  Efficient Techniques for Maintaining Multidimensional Keys in Linked Data Structures. 372-381
  
• Arvind Gupta, Damon Kaller, Thomas C. Shermer:
  On the Complements of Partial k-Trees. 382-391
  
• Mikael Hammar, Bengt J. Nilsson:
  Approximation Results for Kinetic Variants of TSP. 392-401
  
• Yehuda Hassin, David Peleg:
  Distributed Probabilistic Polling and Applications to Proportionate Agreement. 402-411
  
• Yoram Hirshfeld, Mark Jerrum:
  Bisimulation Equivanlence Is Decidable for Normed Process Algebra. 412-421
  
• Yoram Hirshfeld, Alexander Moshe Rabinovich:
  A Framework for Decidable Metrical Logics. 422-432
  
• Juraj Hromkovic, Georg Schnitger:
  On the Power of Las Vegas II. Two-Way Finite Automata. 433-442
  
• Kazuo Iwama, David Manlove, Shuichi Miyazaki, Yasufumi Morita:
  Stable Marriage with Incomplete Lists and Ties. 443-452
  
• Tao Jiang, Ming Li, Paul M. B. Vitányi:
  Average-Case Complexity of Shellsort. 453-462
  
• Dong Kyue Kim, Kunsoo Park:
  Linear-Time Construction of Two-Dimensional Suffix Trees. 463-472
  
• Daniel Kirsten:
  A Connection between the Star Problem and the Finite Power Property in Trace Monoids. 473-482
  
• Daniel Kirsten, Jerzy Marcinkowski:
  Two Techniques in the Area of the Star Problem. 483-492
  
• Matthias Krause, Petr Savický, Ingo Wegener:
  Approximations by OBDDs and the Variable Ordering Problem. 493-502
  
• Antonín Kucera, Richard Mayr:
  Simulation Preorder on Simple Process Algebras. 503-512
  
• Cosimo Laneve, Björn Victor:
  Solos in Concert. 513-523
  
• Mark Lanthier, Anil Maheshwari, Jörg-Rüdiger Sack:
  Shortest Anisotropic Paths on Terrains. 524-533
  
• Arto Lepistö:
  Relations between Local and Global Periodicity of Words. 534-543
  
• Andrzej Lingas, Hans Olsson, Anna Östlin:
  Efficient Merging, Construction, and Maintenance of Evolutionary Trees. 544-553
  
• Marino Miculan:
  Formalizing a Lazy Substitution Proof System for µ-calculus in the Calculus of Inductive Constructions. 554-564
  
• Codrin M. Nichitiu, Eric Rémila:
  Leader Election by d Dimensional Cellular Automata. 565-574
  
• Rolf Niedermeier, Peter Rossmanith:
  New Upper Bounds for MaxSat. 575-584
  
• Vadim Olshevsky, Victor Y. Pan:
  Polynomial and Rational Evaluation and Interpolation (with Structured Matrices). 585-594
  
• Rasmus Pagh:
  Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time. 595-604
  
• Timo Peichl, Heribert Vollmer:
  Finite Automata with Generalized Acceptance Criteria. 605-614
  
• David Peleg, Eilon Reshef:
  A Variant of the Arrow Distributed Directory with Low Average Complexity. 615-624
  
• John Power, Hayo Thielecke:
  Closed Freyd- and kappa-categories. 625-634
  
• Jon G. Riecke, Hayo Thielecke:
  Typed Exeptions and Continuations Cannot Macro-Express Each Other. 635-644
  
• Jan J. M. M. Rutten:
  Automata, Power Series, and Coinduction: Taking Input Derivatives Seriously. 645-654
  
• Peter Sanders:
  Accessing Multiple Sequences Through Set Associative Caches. 655-664
  
• Géraud Sénizergues:
  T(A) = T(B)? 665-675
  
• Mario Szegedy:
  Many-Valued Logics and Holographic Proofs. 676-686
  
• Christopher Umans:
  On the Complexity and Inapproximability of Shortest Implicant Problems. 687-696
  
• Klaus Weihrauch, Ning Zhong:
  The Wave Propagator Is Turing Computable. 697-707
  
• Gerhard J. Woeginger:
  An FPTAS for Agreeably Weighted Variance on a Single Machine. 707-716
  
• Alexandre Tiskin:
  Erratum: Bulk-synchronous Parallel Multiplication of Boolean Matrices. 717-718