26. ICALP 1999:
Prague, Czech Republic
Jirí Wiedermann, Peter van Emde Boas, Mogens Nielsen (Eds.):
Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings.
Lecture Notes in Computer Science 1644 Springer 1999, ISBN 3-540-66224-3
Invited Talks
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

Last update Sat May 18 12:54:46 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page