25. ICALP 1998: Aalborg, Denmark

Kim Guldstrand Larsen, Sven Skyum, Glynn Winskel (Eds.): Automata, Languages and Programming, 25th International Colloquium, ICALP'98, Aalborg, Denmark, July 13-17, 1998, Proceedings. Lecture Notes in Computer Science 1443 Springer 1998, ISBN 3-540-64781-3 BibTeX

@proceedings{DBLP:conf/icalp/1998,
  editor    = {Kim Guldstrand Larsen and
               Sven Skyum and
               Glynn Winskel},
  title     = {Automata, Languages and Programming, 25th International Colloquium,
               ICALP'98, Aalborg, Denmark, July 13-17, 1998, Proceedings},
  booktitle = {ICALP},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1443},
  year      = {1998},
  isbn      = {3-540-64781-3},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Lecture

Yonit Kesten, Amir Pnueli, Li-on Raviv:
Algorithmic Verification of Linear Temporal Logic Specifications. 1-16
Electronic Edition (Springer LINK) BibTeX

Complexity

Bernd Borchert, Dietrich Kuske, Frank Stephan:
On Existentially First-Order Definable Languages and Their Relation to NP. 17-28
Electronic Edition (Springer LINK) BibTeX
Jean-François Raymond, Pascal Tesson, Denis Thérien:
An Algebraic Approach to Communication Complexity. 29-40
Electronic Edition (Springer LINK) BibTeX

Verification

Rajeev Alur, Kenneth L. McMillan, Doron Peled:
Deciding Global Partial-Order Properties. 41-52
Electronic Edition (Springer LINK) BibTeX
Xinxin Liu, Scott A. Smolka:
Simple Linear-Time Algorithms for Minimal Fixed Points (Extended Abstract). 53-66
Electronic Edition (Springer LINK) BibTeX

Data Structures

Thore Husfeldt, Theis Rauhe:
Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method. 67-78
Electronic Edition (Springer LINK) BibTeX
Torben Hagerup:
Simpler and Faster Dictionaries on the AC⁰ RAM. 79-90
Electronic Edition (Springer LINK) BibTeX

Concurrency

Slawomir Lasota:
Partial-Congruence Factorization of Bisimilarity Induced by Open Maps. 91-102
Electronic Edition (Springer LINK) BibTeX
Catherine Dufourd, Alain Finkel, Ph. Schnoebelen:
Reset Nets Between Decidability and Undecidability. 103-115
Electronic Edition (Springer LINK) BibTeX

Invited Lecture

Mark H. Overmars:
Geometric Algorithms for Robotic Manipulation. 116-117
Electronic Edition (Springer LINK) BibTeX

Computational Geormetry

Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, Hsueh-I Lu:
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses. 118-129
Electronic Edition (Springer LINK) BibTeX
Thorsten Graf, Kamakoti Veezhinathan:
Reducing Simple Polygons to Triangles - A Proof for an Improved Conjecture. 130-139
Electronic Edition (Springer LINK) BibTeX

Automata and Temporal Logic

Igor Walukiewicz:
Difficult Configurations - On the Complexity of LTrL. 140-151
Electronic Edition (Springer LINK) BibTeX
Bernard Boigelot, Stéphane Rassart, Pierre Wolper:
On the Expressiveness of Real and Integer Arithmetic Automata (Extended Abstract). 152-163
Electronic Edition (Springer LINK) BibTeX

Algorithms

David Peleg:
Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees. 164-175
Electronic Edition (Springer LINK) BibTeX
Magnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle:
Independent Sets with Domination Constraints. 176-187
Electronic Edition (Springer LINK) BibTeX

Infinite State Systems

Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni:
Robust Asynchronous Protocols Are Finite-State. 188-199
Electronic Edition (Springer LINK) BibTeX
Petr Jancar, Antonín Kucera, Richard Mayr:
Deciding Bisimulation-Like Equivalences with Finite-State Processes. 200-211
Electronic Edition (Springer LINK) BibTeX

Invited Lecture

Avi Wigderson:
Do Probabilistic Algorithms Outperform Deterministic Ones? 212-214
Electronic Edition (Springer LINK) BibTeX

Complexity

Vince Grolmusz:
A Degree-Decreasing Lemma for (MOD q - MOD p) Circuits. 215-222
Electronic Edition (Springer LINK) BibTeX
Chi-Jen Lu:
Improved Pseudorandom Generators for Combinatorial Rectangles. 223-234
Electronic Edition (Springer LINK) BibTeX

Verification

Amir Pnueli, Ofer Strichman, Michael Siegel:
Translation Validation for Synchronous Languages. 235-246
Electronic Edition (Springer LINK) BibTeX
Vladimir A. Zakharov:
An Efficient and Unified Approach to the Decidability of Equivalence of Propositional Programs. 247-258
Electronic Edition (Springer LINK) BibTeX

Complexity

Stasys Jukna, Stanislav Zák:
On Branching Programs With Bounded Uncertainty (Extended Abstract). 259-270
Electronic Edition (Springer LINK) BibTeX
Amir M. Ben-Amram, Holger Petersen:
CONS-Free Programs with Tree Input (Extended Abstract). 271-282
Electronic Edition (Springer LINK) BibTeX

Concurrency

Paolo Baldan, Andrea Corradini, Ugo Montanari:
Concatenable Graph Processes: Relating Processes and Derivation Traces. 283-295
Electronic Edition (Springer LINK) BibTeX
Fabio Gadducci, Ugo Montanari:
Axioms for Contextual Net Processes. 296-308
Electronic Edition (Springer LINK) BibTeX

Invited Lecture

Andrew M. Pitts:
Existential Types: Logical Relations and Operational Equivalence. 309-326
Electronic Edition (Springer LINK) BibTeX

Algorithms

Conrado Martínez, Salvador Roura:
Optimal Sampling Strategies in Quicksort. 327-338
Electronic Edition (Springer LINK) BibTeX
Martin E. Dyer, Catherine S. Greenhill:
A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables. 339-350
Electronic Edition (Springer LINK) BibTeX

Semantics

John Power, Giuseppe Rosolini:
A Modular Approach to Denotational Semantics. 351-362
Electronic Edition (Springer LINK) BibTeX
Pasquale Malacaria, Chris Hankin:
Generalised Flowcharts and Games. 363-374
Electronic Edition (Springer LINK) BibTeX

Approximation

Ming-Yang Kao, Jie Wang:
Efficient Minimization of Numerical Summation Errors. 375-386
Electronic Edition (Springer LINK) BibTeX
Cristina Bazgan, Miklos Santha, Zsolt Tuza:
Efficient Approximation Algorithms for the Subset-Sums Equality Problem. 387-396
Electronic Edition (Springer LINK) BibTeX

Theorem Proving

Eduardo Giménez:
Structural Recursive Definitions in Type Theory. 397-408
Electronic Edition (Springer LINK) BibTeX
Denis Lugiez:
A Good Class of Tree Automata and Application to Inductive Theorem Proving. 409-420
Electronic Edition (Springer LINK) BibTeX

Formal Languages

Juhani Karhumäki, Arto Lepistö, Wojciech Plandowski:
Locally Periodic Infinite Words and a Chaotic Behaviour. 421-430
Electronic Edition (Springer LINK) BibTeX
Jean-Eric Pin:
Bridges for Concatenation Hierarchies. 431-442
Electronic Edition (Springer LINK) BibTeX

Pi-calculus

Huimin Lin:
Complete Proof Systems for Observation Congruences in Finite-Control pi-Calculus. 443-454
Electronic Edition (Springer LINK) BibTeX
Björn Victor, Joachim Parrow:
Concurrent Constraints in the Fusion Calculus. 455-469
Electronic Edition (Springer LINK) BibTeX

Automata and BSP

Michele D'amico, Giovanni Manzini, Luciano Margara:
On Computing the Entropy of Cellular Automata. 470-481
Electronic Edition (Springer LINK) BibTeX
Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery Westbrook:
On the Determinization of Weighted Finite Automata. 482-493
Electronic Edition (Springer LINK) BibTeX
Alexandre Tiskin:
Bulk-Synchronous Parallel Multiplication of Boolean Matrices. 494-506
Electronic Edition (Springer LINK) BibTeX

Rewriting

Hélène Touzet:
A Complex Example of a Simplifying Rewrite System. 507-517
Electronic Edition (Springer LINK) BibTeX
Paul-André Melliès:
On a Duality Between Kruskal and Dershowitz Theorems. 518-529
Electronic Edition (Springer LINK) BibTeX
Daria Walukiewicz: A Total AC-Compatible Reduction Ordering on Higher-Order Terms. 530-542 BibTeX

Invited Lecture

Thomas A. Henzinger:
Model Checking Game Properties of Multi-agent Systems (Abstract). 543
Electronic Edition (Springer LINK) BibTeX

Networks and Routing

Luisa Gargano:
Limited Wavelength Conversion in All-Optical Tree Networks. 544-555
Electronic Edition (Springer LINK) BibTeX
Shiva Chaudhuri, K. V. Subrahmanyam, Frank Wagner, Christos D. Zaroliagis:
Computing Mimicking Networks. 556-567
Electronic Edition (Springer LINK) BibTeX

Real Time

Christel Baier, Joost-Pieter Katoen, Diego Latella:
Metric Semantics for True Concurrent Real Time. 568-579
Electronic Edition (Springer LINK) BibTeX
Thomas A. Henzinger, Jean-François Raskin, Pierre-Yves Schobbens:
The Regular Real-Time Languages. 580-591
Electronic Edition (Springer LINK) BibTeX

Networks and Routing

Serafino Cicerone, Gabriele Di Stefano, Michele Flammini:
Static and Dynamic Low-Congested Interval Routing Schemes. 592-603
Electronic Edition (Springer LINK) BibTeX
Doug Cook, Vance Faber, Madhav V. Marathe, Aravind Srinivasan, Yoram J. Sussmann:
Low-Bandwidth Routing and Electrical Power Networks. 604-615
Electronic Edition (Springer LINK) BibTeX

Automata and Temporal Logic

Fritz Henglein, Jakob Rehof:
Constraint Automata and the Complexity of Recursive Subtype Entailment. 616-627
Electronic Edition (Springer LINK) BibTeX
Moshe Y. Vardi:
Reasoning about The Past with Two-Way Automata. 628-641
Electronic Edition (Springer LINK) BibTeX

Invited Lecture

Leslie G. Valiant:
A Neuroidal Architecture for Cognitive Computation. 642-669
Electronic Edition (Springer LINK) BibTeX

Approximation

David Peleg, Eilon Reshef:
Deterministic Polylog Approximation for Minimum Communication Spanning Trees. 670-681
Electronic Edition (Springer LINK) BibTeX
Artur Czumaj, Andrzej Lingas:
A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity. 682-694
Electronic Edition (Springer LINK) BibTeX

Pi-calculus

Peter Sewell:
Global/Local Subtyping and Capability Inference for a Distributed pi-calculus. 695-706
Electronic Edition (Springer LINK) BibTeX
Zhoujun Li, Huowang Chen:
Checking Strong/Weak Bisimulation Equivalences and Observation Congruence for the pi-Calculus. 707-718
Electronic Edition (Springer LINK) BibTeX

Algorithms

Dario Bini, Gianna M. Del Corso, Giovanni Manzini, Luciano Margara:
Inversion of Circulant Matrices over Z_m. 719-730
Electronic Edition (Springer LINK) BibTeX
Wojciech Plandowski, Wojciech Rytter:
Application of Lempel-Ziv Encodings to the Solution of Words Equations. 731-742
Electronic Edition (Springer LINK) BibTeX

Theorem Proving

Neil Ghani, Valeria de Paiva, Eike Ritter:
Explicit Substitutions for Constructive Necessity. 743-754
Electronic Edition (Springer LINK) BibTeX
Gilles Barthe:
The Relevance of Proof-Irrelevance. 755-768
Electronic Edition (Springer LINK) BibTeX

Invited Lecture

Gilles Brassard:
New Horizons in Quantum Information Processing. 769-771
Electronic Edition (Springer LINK) BibTeX

Zero-Knowledge

Ivan Damgård, Birgit Pfitzmann:
Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP. 772-783
Electronic Edition (Springer LINK) BibTeX
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung:
Image Density is Complete for Non-Interactive-SZK (Extended Abstract). 784-795
Electronic Edition (Springer LINK) BibTeX

Semantics

Peter Hertling, Klaus Weihrauch:
Randomness Spaces. 796-807
Electronic Edition (Springer LINK) BibTeX
Antonio Bucciarelli, Ivano Salvo:
Totality, Definability and Boolean Ciruits. 808-819
Electronic Edition (Springer LINK) BibTeX

Quantum Computing and Computational Biology

Gilles Brassard, Peter Høyer, Alain Tapp:
Quantum Counting. 820-831
Electronic Edition (Springer LINK) BibTeX
Tatsuya Akutsu, Mutsunori Yagiura:
On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biology. 832-843
Electronic Edition (Springer LINK) BibTeX

Pi-calculus

Cédric Fournet, Georges Gonthier:
A Hierarchy of Equivalences for Asynchronous Calculi. 844-855
Electronic Edition (Springer LINK) BibTeX
Massimo Merro, Davide Sangiorgi:
On Asynchrony in Name-Passing Calculi. 856-867
Electronic Edition (Springer LINK) BibTeX

Invited Lecture

Martín Abadi:
Protection in Programming-Language Translations. 868-883
Electronic Edition (Springer LINK) BibTeX

Automata

Holger Petersen, John Michael Robson:
Efficient Simulations by Queue Machines. 884-895
Electronic Edition (Springer LINK) BibTeX
Pavol Duris, Tomasz Jurdzinski, Miroslaw Kutylowski, Krzysztof Lorys:
Power of Cooperation and Multihead Finite Systems. 896-907
Electronic Edition (Springer LINK) BibTeX

Programming Languages and Types

Olivier Danvy:
A Simple Solution to Type Specialization. 908-917
Electronic Edition (Springer LINK) BibTeX
Walid Taha, Zine-El-Abidine Benaissa, Tim Sheard:
Multi-Stage Programming: Axiomatization and Type Safety. 918-929
Electronic Edition (Springer LINK) BibTeX