21. ICALP 1994: Jerusalem, Israel

Serge Abiteboul, Eli Shamir (Eds.): Automata, Languages and Programming, 21st International Colloquium, ICALP94, Jerusalem, Israel, July 11-14, 1994, Proceedings. Lecture Notes in Computer Science 820 Springer 1994, ISBN 3-540-58201-0

Theory of Computation

Pavel Pudlák:
Unexpected Upper Bounds on the Complexity of Some Communication Games. 1-10
Henning Fernau, Ludwig Staiger:
Valuations and Unambiguity of Languages, with Applications to Fractal Geometry. 11-22
Hava T. Siegelmann:
On The Computational Power of Probabilistic and Faulty Neural Networks. 23-34

Automata, Computation Models

Karlis Cerans:
Deciding Properties of Integral Relational Automata. 35-46
Yonatan Aumann, Judit Bar-Ilan, Uriel Feige:
On the Cost of Recomputing: Tight Bounds on Pebbling with Faults. 47-58
Eugene Asarin, Oded Maler:
On some Relations between Dynamical Systems and Transition Systems. 59-72
Noa Globerman, David Harel:
Complexity Results for Multi-Pebble Automata and their Logics. 73-82

Expressive Power

Paris C. Kanellakis, Gerd G. Hillebrand, Harry G. Mairson:
An Analysis of the Core-ML Language: Expressive Power and Type Reconstruction. 83-105
Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht:
Expressiveness of Efficient Semi-Deterministic Choice Constructs. 106-117
Erich Grädel, Yuri Gurevich:
Tailoring Recursing for Complexity. 118-129

Automata, Concurrency

Nils Klarlund, Madhavan Mukund, Milind A. Sohoni:
Determinizing Asynchronous Automata. 130-141
Anca Muscholl:
On the Complementation of Büchi Asynchronous Cellular Automata. 142-153
Flavio Corradini, Rocco De Nicola:
Distribution and Locality of Concurrent Systems. 154-165
Rainer Gawlick, Roberto Segala, Jørgen F. Søgaard-Andersen, Nancy A. Lynch:
Liveness in Timed and Untimed Systems. 166-177

Pattern Matching

José-Ramón Sánchez-Couso, María-Inés Fernández-Camacho:
Average-Case Analysis of Pattern-Matching in Trees under the BST Probability Model. 178-190
Tao Jiang, Ming Li:
On the Approximation of Shortest Common Supersequences and Longest Common Subsequences. 191-202
Ramesh Hariharan, S. Muthukrishnan:
Optimal Parallel Algorithms for Prefix Matching. 203-214
Amihood Amir, Gary Benson, Martin Farach:
Optimal Two-Dimensional Compressed Matching. 215-226

Data Structures

Giuseppe F. Italiano, Rajiv Ramaswami:
Maintaining Spanning Trees of Small Diameter. 227-238
Joseph Gil, Yossi Matias:
Simple Fast Parallel Hashing. 239-250
Teresa M. Przytycka, Lawrence L. Larmore:
The Optimal Alphabetic Tree Problem Revisited. 251-262

Computation Complexity

Harry Buhrman, Leen Torenvliet:
On the Cutting Edge of Relativization: The Resource Bounded Injury Method. 263-273
Jean-Camille Birget, Stuart W. Margolis, John C. Meakin, Pascal Weil:
PSPACE-Completeness of Certain Algorithmic Problems on the Subgroups of Free Groups. 274-285

Semantics, Logic and Verification I

Matthew Hennessy:
Higher-Order Process and Their Models. 286-303
Bart Vergauwen, Johan Lewi:
Efficient Local Correctness Checking for Single and Alternating Boolean Equation Systems. 304-315
Parosh Aziz Abdulla, Bengt Jonsson:
Undecidable Verification Problems for Programs with Unreliable Channels. 316-327
Limor Fix, Fred B. Schneider:
Reasoning about Programs by Exploiting the Environment. 328-339

Semantics, Logic and Verification II

Torben Braüner:
A Model of Intuitionistic Affine Logic From Stable Domain Theory. 340-351
Gordon D. Plotkin, Glynn Winskel:
Bistructures, Bidomains and Linear Logic. 352-363
Adnan Aziz, Vigyan Singhal, Felice Balarin, Robert K. Brayton, Alberto L. Sangiovanni-Vincentelli:
Equivalences for Fair Kripke Structures. 364-375
Franck van Breugel:
Generalized Finiteness Conditions of Labelled Transition Systems. 376-387

Formal Languages

Manfred Droste:
A KLeene Theorem for Recognizable Languages over Concurrency Monoids. 388-399
Helmut Seidl:
Least Solutions of Equations over N. 400-411
Günter Hotz, Gisela Pitsch:
Fast Uniform Analysis of Coupled-Context-Free Languages. 412-423
Jean-Eric Pin:
Polynomial Closure of Group Languages and Open Sets of the Hall Topology. 424-435

Term Rewriting Systems

Anne-Cécile Caron, Hubert Comon, Jean-Luc Coquidé, Max Dauchet, Florent Jacquemard:
Pumping, Cleaning and Symbolic Constraints Solving. 436-449
Claus Hintermeier, Claude Kirchner, Hélène Kirchner:
Dynamically-Typed Computations for Order-Sorted Equational Presentations. 450-461
Roberto Di Cosmo, Delia Kesner:
Combining First Order Algebraic Rewriting Systems, Recursion and Extensional Lambda Calculi. 462-472

Algorithms and Communications

Eli Upfal:
On the Theory of Interconnection Networks for Parallel Computers. 473-486
Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis:
Multiway Cuts in Directed and Node Weighted Graphs. 487-498
Uriel Feige:
A Fast Randomized LOGSPACE Algorithm for Graph Connectivity. 499-507
Sotiris E. Nikoletseas, Krishna V. Palem, Paul G. Spirakis, Moti Yung:
Short Vertex Disjoint Paths and Multiconnectivity in Random Graphs: Reliable Network Computing. 508-519

Graph Algorithms

Jens Lagergren:
The Size of an Interwine. 520-531
Raphael Yuster, Uri Zwick:
Finding Even Cycles Even Faster. 532-543
Franz Höfting, Egon Wanke:
Polynomial Time Analysis of Torodial Periodic Graphs. 544-555
Paola Bonizzoni:
A Tight Lower Bound for Primitivity in k-Structures. 556-567

Randomized Complexity

Carlo Blundo, Alfredo De Santis, Ugo Vaccaro:
Randomness in Distributed Protocols. 568-579
Rusins Freivalds, Marek Karpinski:
Lower Space Bounds for Randomized Computation. 580-592
Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer, Stephan Weis:
The Average Case Complexity of the Parallel Prefix Problem. 593-604

Various Algorithms

Mordecai J. Golin, Neal E. Young:
Prefix Codes: Equiprobable Words, Unequal Letter Costs. 605-617
C. Greg Plaxton, Torsten Suel:
A Super-Logarithmic Lower Bound for Hypercubic Sorting Networks. 618-629
Aohan Mei, Yoshihide Igarashi:
Efficient Strategies for Robot Navigation in Unknown Environment. 630-641

Last update Sun May 19 22:27:12 2013 CET by the DBLP Team —

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