Automata, Languages and Programming

1. Front Matter

   PDF

2. Program result checking: A new approach to making programs more reliable

   • Manuel Blum

   Pages 1-14

3. Dynamic interpolation search in o(log log n) time

   • Arne Andersson, Christer Mattsson

   Pages 15-27

4. Searching among intervals and compact routing tables

   • Greg N. Frederickson

   Pages 28-39

5. The approximation of maximum subgraph problems

   • Carsten Lund, Mihalis Yannakakis

   Pages 40-51

6. Polynomially bounded minimization problems which are hard to approximate

   • Viggo Kann

   Pages 52-63

7. Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover

   • Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis

   Pages 64-75

8. The complexity of approximating PSPACE-complete problems for hierarchical specifications

   • M. V. Marathe, H. B. Hunt III, S. S. Ravi

   Pages 76-87

9. Problems on pairs of trees and the four colour problem of planar graphs

   • Artur Czumaj, Alan Gibbons

   Pages 88-101

10. Constructing competitive tours from local information

    • Bala Kalyanasundaram, Kirk R. Pruhs

    Pages 102-113

11. Treewidth and pathwidth of permutation graphs

    • Hans Bodlaender, Ton Kloks, Dieter Kratsch

    Pages 114-125

12. A theory of even functionals and their algorithmic applications

    • Jerzy W. Jaromczyk, Grzegorz Świcatek

    Pages 126-136

13. Exact asymptotics of divide-and-conquer recurrences

    • Philippe Flajolet, Mordecai Golin

    Pages 137-149

14. Optimal bounds for the change-making problem

    • Dexter Kozen, Shmuel Zaks

    Pages 150-161

15. The complexity of N-body simulation

    • John H. Reif, Stephen R. Tate

    Pages 162-176

16. A simple method for resolving degeneracies in Delaunay triangulations

    • Michael B. Dillencourt, Warren D. Smith

    Pages 177-188

17. Fault-tolerance and complexity (Extended abstract)

    • Lane A. Hemachandra

    Pages 189-202

18. Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines

    • Hiroaki Yamamoto

    Pages 203-214

19. On the computational power of discrete Hopfield nets

    • Pekka Orponen

    Pages 215-226

20. On randomized versus deterministic computation

    • Marek Karpinski, Rutger Verbeek

    Pages 227-240

The International Colloquium on Automata, Languages and Programming (ICALP) is an annual conference series sponsored by the European Association for Theoretical Computer Science (EATCS). It is intended to cover all important areas of theoretical computer science, such as: computability, automata,formal languages, term rewriting, analysis of algorithms, computational geometry, computational complexity, symbolic and algebraic computation, cryptography, data types and data structures, theory of data bases and knowledge bases, semantics of programming languages, program specification, transformation and verification, foundations of logicprogramming, theory of logical design and layout, parallel and distributed computation, theory of concurrency, and theory of robotics. This volume contains the proceedings of ICALP 93, held at LundUniversity, Sweden, in July 1993. It includes five invited papers and 51 contributed papers selected from 151 submissions.

• Automat
• algorithms
• automata
• complexity
• computer science
• data structure
• data structures
• formal language
• programming
• programming language
• robot
• robotics
• semantics
• term rewriting
• verification
• algorithm analysis and problem complexity

Policies and ethics