search for books and compare prices
Tables of Contents for Automata, Languages & Programming
Chapter/Section Title
Page #
Page Count
Invited Talk: Game Semantics: Achievements and Prospects
1
1
Samson Abramsky
Clique Is Hard to Approximate within n1-o(1)
2
11
Lars Engebretsen
Jonas Holmerin
Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time
13
12
Michael Krivelevich
Van H. Vu
Closed Types as a Simple Approach to Safe Imperative Multi-stage Programing
25
12
Cristiano Calcagno
Eugenio Moggi
Walid Taha
A Statically Allocated Parallel Functional Language
37
12
Alan Mycroft
Richard Sharp
An Optimal Minimum Spanning Tree Algorithm
49
12
Seth Pettie
Vijaya Ramachandran
Improved Shortest Paths on the Word RAM
61
12
Torben Hagerup
Improved Algorithms for Finding Level Ancestors in Dynamic Trees
73
12
Stephen Alstrup
Jacob Holm
Lax Logical Relations
85
18
Gordon Plotkin
John Power
Donald Sannella
Robert Tennent
Reasoning about Idealized Algol Using Regular Languages
103
13
Dan R. Ghica
Guy McCusker
The Measurement Process in Domain Theory
116
11
Keye Martin
Invited Talk: Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution
127
24
Gregor Engels
Reiko Heckel
Monotone Proofs of the Pigeon Hole Principle
151
12
Albert Atserias
Nicola Galesi
Ricard Gavalda
Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models
163
12
Gerald Luttgen
Michael Mendler
Algebraic Models for Contextual Nets
175
12
Roberto Bruni
Vladimiro Sassone
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems
187
12
Beate Bollig
Ingo Wegener
Measures of Nondeterminism in Finite Automata
199
12
Juraj Hromkovic
Juhani Karhumaki
Hartmut Klauck
Georg Schnitger
Sebastian Seibert
LTL Is Expressively Complete for Mazurkiewicz Traces
211
12
Volker Diekert
Paul Gastin
An Automata-Theoretic Completeness Proof for Interval Temporal Logic
223
12
Ben C. Moszkowski
Invited Talk: Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?
235
1
Johan Hastad
Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search
236
12
Evgeny Dantsin
Andreas Goerdt
Edward A. Hirsch
sUwe Schoning
Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices
248
12
Johannes Blomer
Variable Independence, Quantifier Elimination, and Constraint Representations
260
12
Leonid Libkin
Constraint Satisfaction Problems and Finite Algebras
272
11
Andrei A. Bulatov
Andrei A. Krokhin
Peter Jeavons
An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing
283
13
Steven S. Seiden
Resource Augmentation for Online Bounded Space Bin Packing
296
9
Janos Csirik
Gerhard J. Woeginger
Optimal Projective Algorithms for the List Update Problem
305
12
Christoph Ambuhl
Bernd Gartner
Bernhard von Stengel
Efficient Verification Algorithms for One-Counter Processes
317
12
Antonin Kucera
On the Complexity of Bisimulation Problems for Basic Parallel Processes
329
13
Richard Mayr
Decidable First-Order Transition Logics for PA-Processes
342
12
Denis Lugiez
Philippe Schnoebelen
Invited Talk: Non Interference for the Analysis of Cryptographic Protocols
354
19
Riccardo Focardi
Roberto Gorrieri
Fabio Martinelli
Average Bit-Complexity of Euclidean Algorithms
373
15
Ali Akhavi
Brigitte Vallee
Planar Maps and Airy Phenomena
388
15
Cyril Banderier
Philippe Flajolet
Gilles Schaeffer
Michele Soria
Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System
403
12
Barbara Konig
Information Flow vs. Resource Access in the Asynchronous Pi-Calculus
415
13
Matthew Hennessy
James Riely
Award Talk: The Genomics Revolution and Its Challenges for Algorithmic Research
428
1
Richard M. Karp
Invited Talk: Alternating the Temporal Picture for Safety
429
22
Zohar Manna
Henny B. Sipma
Necessary and Sufficient Assumptions for Non-interactive Zero-Knowledge Proofs of Knowledge for All NP Relations
451
12
Alfredo De Santis
Giovanni Di Crescenzo
Giuseppe Persiano
Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP
463
12
William Aiello
Sandeep Bhatt
Rafail Ostrovsky
S. Raj Rajagopalan
A New Unfolding Approach to LTL Model Checking
475
12
Javier Esparza
Keijo Heljanko
Reasoning about Message Passing in Finite State Environments
487
12
B. Meenakshi
R. Ramanujam
Extended Notions of Security for Multicast Public Key Cryptosystems
499
13
Olivier Baudron
David Pointcheval
Jacques Stern
One-Round Secure Computation and Secure Autonomous Mobile Agents
512
12
Christian Cachin
Jan Camenisch
Joe Kilian
Joy Muller
Round-Optimal and Abuse Free Optimistic Multi-party Contract Signing
524
12
Birgit Baum-Waidner
Michael Waidner
On the Centralizer of a Finite Set
536
11
Juhani Karhumaki
Ion Petre
On the Power of Tree-Walking Automata
547
14
Frank Neven
Thomas Schwentick
Determinization of Transducers over Infinite Words
561
10
Marie-Pierre Beal
Olivier Carton
Invited Talk: Constraint Programming and Graph Algorithms
571
5
Kurt Mehlhorn
Scalable Secure Storage when Half the System Is Faulty
576
12
Noga Alon
Haim Kaplan
Michael Krivelevich
Dahlia Malkhi
Julien Stern
Generating Partial and Multiple Transversals of a Hypergraph
588
12
Endre Boros
Vladimir Gurvich
Leonid Khachiyan
Kazuhisa Makino
Revisiting the Correspondence between Cut Elimination and Normalisation
600
12
Jose Espirito Santo
Negation Elimination from Simple Equational Formulae
612
12
Reinhard Pichler
Hardness of Set Cover with Intersection 1
624
12
V.S. Anil Kumar
Sunil Arya
H. Ramesh
Strong Inapproximability of the Basic k-Spanner Problem
636
12
Michael Elkin
David Peleg
Infinite Series-Parallel Posets: Logic and Languages
648
15
Dietrich Kuske
On Deciding if Deterministic Rabin Language Is in Buchi Class
663
12
Tomasz Fryderyk Urbanski
On Message Sequence Graphs and Finitely Generated Regular MSC Languages
675
12
Jesper G. Henriksen
Madhavan Mukund
K. Narayan Kumar
P.S. Thiagarajan
Invited Talk: Pseudorandomness
687
18
Oded Goldreich
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols
705
12
Leslie Ann Goldberg
Mark Jerrum
Sampath Kannan
Mike Paterson
Deterministic Radio Broadcasting
717
12
Bogdan S. Chlebus
Leszek Gasieniec
Anna Ostlin
John Michael Robson
An ω-Complete Equational Specification of Interleaving
729
15
W.J. Fokkink
S.P. Luttik
A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors
744
12
Mario Bravetti
Roberto Gorrieri
Tight Size Bounds for Packet Headers in Narrow Meshes
756
12
Micah Adler
Faith Fich
Leslie Ann Goldberg
Mike Paterson
Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link
768
12
Luciano Margara
Janos Simon
On the Logical Characterisation of Performability Properties
780
13
Christel Baier
Boudewijn Haverkort
Holger Hermanns
Joost-Pieter Katoen
On the Representation of Timed Polyhedra
793
15
Olivier Bournez
Oded Maler
Invited Talk: Min-wise Independent Permutations: Theory and Practice
808
1
Andrei Z. Broder
Testing Acyclicity of Directed Graphs in Sublinear Time
809
12
Michael A. Bender
Dana Ron
Computing the Girth of a Planar Graph
821
11
Hristo N. Djidjev
Lower Bounds Are Not Easier over the Reals: Inside PH
832
12
Herve Fournier
Pascal Koiran
Unlearning Helps
844
12
Ganesh Baliga
John Case
Wolfgang Merkle
Frank Stephan
Fast Approximation Schemes for Euclidean Multi-connectivity Problems
856
13
Artur Czumaj
Andrzej Lingas
Approximate TSP in Graphs with Forbidden Minors
869
9
Michelangelo Grigni
Polynomial Time Approximation Schemes for General Multiprocessor Job Shop Scheduling
878
12
Klaus Jansen
Lorant Porkolab
The Many Faces of a Translation
890
12
Pierre McKenzie
Thomas Schwentick
Denis Therien
Heribert Vollmer
Gales and the Constructive Dimension of Individual Sequences
902
12
Jack H. Lutz
The Global Power of Additional Queries to p-Random Oracles
914
12
Wolfgang Merkle
Homogenization and the Polynomial Calculus
926
13
Josh Buresh-Oppenheim
Matt Clegg
Russell Impagliazzo
Toniann Pitassi
Author Index
939