20. ICALP 1993: Lund, Sweden

Andrzej Lingas, Rolf G. Karlsson, Svante Carlsson (Eds.): Automata, Languages and Programming, 20nd International Colloquium, ICALP93, Lund, Sweden, July 5-9, 1993, Proceedings. Lecture Notes in Computer Science 700 Springer 1993, ISBN 3-540-56939-1

Programs and Data Structures

Manuel Blum:
Program Result Checking: A New Approach to Making Programs More Reliable. 1-14
Arne Andersson, Christer Mattsson:
Dynamic Interpolation Search in o(log log n) Time. 15-27
Greg N. Frederickson:
Searching among Intervals and Compact Routing Tables. 28-39

Carsten Lund, Mihalis Yannakakis:
The Approximation of Maximum Subgraph Problems. 40-51
Viggo Kann:
Polynomially Bounded Minimization Problems which are Hard to Approximate. 52-63
Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis:
Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover. 64-75
Madhav V. Marathe, Harry B. Hunt III, S. S. Ravi:
The Complexity of Approximating PSPACE-Complete Problems for Hierarchical Specifications (Extended Abstract). 76-87

Artur Czumaj, Alan Gibbons:
Problems on Pairs of Trees and the Four Colour Problem of Planar Graphs. 88-101
Bala Kalyanasundaram, Kirk Pruhs:
Constructing Competitive Tours From Local Information. 102-113
Hans L. Bodlaender, Ton Kloks, Dieter Kratsch:
Treewidth and Pathwidth of Permutation Graphs. 114-125
Jerzy W. Jaromczyk, Grzegorz Swiatek:
A Theory of Even Functionals and Their Algorithmic Applications. 126-136

Philippe Flajolet, Mordecai J. Golin:
Exact Asymptotics of Divide-and-Conquer Recurrences. 137-149
Dexter Kozen, Shmuel Zaks:
Optimal Bounds for the Change-Making Problem. 150-161
John H. Reif, Stephen R. Tate:
The Complexity of N-body Simulation. 162-176
Michael B. Dillencourt, Warren D. Smith:
A Simple Method for Resolving Degeneracies in Delaunay Triangulations. 177-188

Lane A. Hemachandra:
Fault-Tolerance and Complexity (Extended Abstract). 189-202
Hiroaki Yamamoto:
Reversal-Space Trade-offs For Simultaneous Resource-Bounded Nondeterministic Turing Machines. 203-214
Pekka Orponen:
On the Computational Power of Discrete Hopfield Nets. 215-226

Marek Karpinski, Rutger Verbeek:
On Randomized Versus Deterministic Computation. 227-240
Farid M. Ablayev:
Lower Bounds for One-way Probabilistic Communication Complexity. 241-252
Torben Hagerup, Kurt Mehlhorn, J. Ian Munro:
Maintaining Discrete Probability Distributions Optimally. 253-264
Matthew K. Franklin, Moti Yung:
Secure and Efficient Off-Line Digital Money (Extended Abstract). 265-276

David W. Juedes, James I. Lathrop, Jack H. Lutz:
Computational Depth and Reducibility (Extended Abstract). 277-288
Ganesh Baliga, John Case:
Learnability: Admissible, Co-finite, and Hypersimple Languages. 289-300
Tao Jiang, Arto Salomaa, Kai Salomaa, Sheng Yu:
Inclusion is Undecidable for Pattern Languages. 301-312
Oscar H. Ibarra, Tao Jiang, Nicholas Q. Trân, Hui Wang:
New Decidability Results Concerning Two-way Counter Machines and Applications. 313-324

Christian Michaux, Roger Villemaire:
Cobham's Ttheorem seen through Büchi's Theorem. 325-334
Werner Ebinger, Anca Muscholl:
Logical Definability on Infinite Traces. 335-346
Thomas Wilke:
Algebras for Classifying Regular Tree Languages and an Application to Frontier Testability. 347-358
Arvind Gupta:
Finite Automata as Characterizations of Minor Closed Tree Families (Extended Abstract). 359-370

Danny Dolev, Dalia Malki:
On Distributed Algorithms in a Broadcast Domain. 371-387
Bogdan S. Chlebus, Krzysztof Diks, Andrzej Pelc:
Sparse Networks Supporting Efficient Reliable Broadcasting. 388-397

Friedhelm Meyer auf der Heide, Brigitte Oesterdiekhoff, Rolf Wanka:
Strongly Adaptive Token Distribution. 398-409
Arnold Schönhage:
Fast Parallel Computation of Characteristic Polynomials by Leverrier's POwer Sum Method Adapted to Fields of Finite Characteristic. 410-417
Lefteris M. Kirousis:
Fast Parallel Constraint Satisfaction. 418-429

Imre Simon:
The Product of Rational Languages. 430-444
Edward Ochmanski, Pierre-André Wacrenier:
On Regular Compatibility of Semi-Commutations. 445-456
Philippe Dumas:
Algebraic Aspects of B-regular Series. 457-468

David M. Cohen, Michael L. Fredman:
Products of Finite State Machines with Full Coverage. 469-477
Géraud Sénizergues:
An Effective Version of Stallings' Theorem in the Case of Context-Free Groups. 478-495
Arto Lepistö:
On the Power of Periodic Iteration of Morphisms. 496-506
Filippo Mignosi, Patrice Séébold:
If a D0L Language is k-Power Free then it is Circular. 507-518

Lalita Jategaonkar, Albert R. Meyer:
Deciding True Concurrency Equivalences on Finite Sate Nets (Preliminary Report). 519-531
Walter Vogler:
Timed Testing of Concurrent Systems. 532-543
Klaus Havelund, Kim Guldstrand Larsen:
The Fork Calculus. 544-557
Paola Inverardi, Corrado Priami, Daniel Yankelevich:
Extended Transition Systems for Parametric Bisimulation. 558-569

Carolyn Brown, Doug Gurr:
Temporal Logic and Categories of Petrie Nets. 570-581
Kamal Lodaya, P. S. Thiagarajan:
Decidability of a Partial Order Based Temporal Logic. 582-592
Hardi Hungar, Bernhard Steffen:
Local Model Checking for Context-Free Processes. 593-605

Serge Abiteboul, Victor Vianu:
Computing on Structures. 606-620
Evelyne Contejean:
A Partial Solution for D-Unification Based on a Reduction to AC1-Unification. 621-632
Michael Codish, Moreno Falaschi, Kim Marriott, William H. Winsborough:
Efficient Analysis of Concurrent Constraint Logic Programs. 633-644

Roberto Di Cosmo, Delia Kesner:
A Confluent Reduction for the Extensional Typed lambda-Calculus with Pairs, Sums, Recursion and terminal Object. 645-656
Franco Barbanera, Maribel Fernández:
Modularity of Termination and Confluence in Combinations of Rewrite Systems with lambda_omega. 657-668
Felipe Bracho, Manfred Droste:
From Domains to Automata with Concurrency. 669-681
Ramarao Kanneganti, Robert Cartwright:
What is a Universal Higher-Order Programming Language? 682-695