Automata, Languages and Programming

1. Front Matter

   PDF

2. Algorithmic verification of linear temporal logic specifications

   • Yonit Kesten, Amir Pnueli, Li-on Raviv

   Pages 1-16

3. On existentially first-order definable languages and their relation to NP

   • Bernd Borchert, Dietrich Kuske, Frank Stephan

   Pages 17-28

4. An algebraic approach to communication complexity

   • Jean-FranÇois Raymond, Pascal Tesson, Denis Thérien

   Pages 29-40

5. Deciding global partial-order properties

   • Rajeev Alur, Ken McMillan, Doron Peled

   Pages 41-52

6. Simple linear-time algorithms for minimal fixed points

   • Xinxin Liu, Scott A. Smolka

   Pages 53-66

7. Hardness results for dynamic problems by extensions of Fredman and Saks' chronogram method

   • Thore Husfeldt, Theis Rauhe

   Pages 67-78

8. Simpler and faster dictionaries on the AC0 RAM

   • Torben Hagerup

   Pages 79-90

9. Partial-congruence factorization of bisimilarity induced by open maps

   • Slawomir Lasota

   Pages 91-102

10. Reset nets between decidability and undecidability

    • C. Dufourd, A. Finkel, Ph. Schnoebelen

    Pages 103-115

11. Geometric algorithms for robotic manipulation

    • Mark H. Overmars

    Pages 116-117

12. Compact encodings of planar graphs via canonical orderings and multiple parentheses

    • Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, Hsueh-I Lu

    Pages 118-129

13. Reducing simple polygons to triangles - A proof for an improved conjecture -

    • Thorsten Graf, Kamakoti Veezhinathan

    Pages 130-139

14. Difficult configurations — on the complexity of LTrL

    • Igor Walukiewicz

    Pages 140-151

15. On the expressiveness of real and integer arithmetic automata

    • Bernard Boigelot, Stéphane Rassart, Pierre Wolper

    Pages 152-163

16. Distributed matroid basis completion via elimination upcast and distributed correction of minimum-weight spanning trees

    • David Peleg

    Pages 164-175

17. Independent sets with domination constraints

    • MagnÚs M. Halldórsson, Jan Kratochvíl, Jan Arne Telle

    Pages 176-187

18. Robust asynchronous protocols are finite-state

    • Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind Sohoni

    Pages 188-199

19. Deciding bisimulation-like equivalences with finite-state processes

    • Petr Jančar, Antonín Kučera, Richard Mayr

    Pages 200-211

20. Do probabilistic algorithms outperform deterministic ones?

    • Avi Wigderson

    Pages 212-214

This book constitutes the refereed proceedings of the 25th International Colloquium on Automata, Languages and Programming, ICALP'98, held in Aalborg, Denmark, in July 1998.
The 70 revised full papers presented together with eight invited contributions were carefully selected from a total of 182 submissions. The book is divided in topical sections on complexitiy, verification, data structures, concurrency, computational geometry, automata and temporal logic, algorithms, infinite state systems, semantics, approximation, thorem proving, formal languages, pi-calculus, automata and BSP, rewriting, networking and routing, zero-knowledge, quantum computing, etc..

• Algorithms
• Concurrency
• Mathematical Logic
• Networking
• Processing
• Text
• programming
• robot
• data structures

Policies and ethics