search for books and compare prices
Tables of Contents for Automata, Languages and Programming
Chapter/Section Title
Page #
Page Count
Keynote Papers
Algorithms, Games, and the Internet
1
3
C.H. Papadimitriou
Automata, Circuits, and Hybrids: Facets of Continuous Time
4
20
B.A. Trakhtenbrot
Invited Papers
Languages, Rewriting Systems, and Verification of Infinite-State Systems
24
16
A. Bouajjani
Integrating Semantics for Object-Oriented System Models
40
21
M. Grobe-Rhode
Modelling with Partial Orders - Why and Why Not?
61
3
M. Nielsen
Theoretical Aspects of Evolutionary Algorithms
64
15
I. Wegener
Algebraic and Circuit Complexity
Improvements of the Alder-Strassen Bound: Algebras with Nonzero Radical
79
13
M. Blaser
On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities
92
12
E. Boros
K. Elbassioni
V. Gurvich
L. Khachiyan
K. Makino
Division Is in Uniform TC0
104
11
W. Hesse
Algorithm Analysis
A Framework for Index Bulk Loading and Dynamization
115
13
P.K. Agarwal
L. Arge
O. Procopiuc
J.S. Vitter
A Characterization of Temporal Locality and Its Portability across Memory Hierarchies
128
12
G. Bilardi
E. Peserico
The Complexity of Constructing Evolutionary Trees Using Experiments
140
12
G.S. Brodal
R. Fagerberg
C.N.S. Pedersen
A. Ostlin
Hidden Pattern Statistics
152
14
P. Flajolet
Y. Guivarch'h
W. Szpankowski
B. Vallee
Combinatorics and Algorithms on Low-Discrepancy Roundings of a Real Sequence
166
12
K. Sadakane
N. Takki-Chebihi
T. Tokuyama
All-Pairs Shortest Paths Computation in the BSP Model
178
12
A. Tiskin
Approximation and Optimization
Approximating the Minimum Spanning Tree Weight in Sublinear Time
190
11
B. Chazelle
R. Rubinfeld
L. Trevisan
Approximation Hardness of TSP with Bounded Metrics
201
12
L. Engebretsen
M. Karpinski
The RPR2 Rounding Technique for Semidefinite Programs
213
12
U. Feige
M. Langberg
Approximation Algorithms for Partial Covering Problems
225
12
R. Gandhi
S. Khuller
A. Srinivasan
On the Online Bin Packing Problem
237
12
S.S. Seiden
Quick k-Median, k-Center, and Facility Location for Sparse Graphs
249
12
M. Thorup
Complexity
Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems
261
12
J. Alber
H. Fernau
R. Niedermeier
Subexponential Parameterized Algorithms Collapse the W-Hierarchy
273
12
L. Cai
D. Juedes
Improved Lower Bounds on the Randomized Complexity of Graph Properties
285
12
A. Chakrabarti
S. Khot
New Imperfect Random Source with Applications to Coin-Flipping
297
13
Y. Dodis
Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently
310
12
J. Friedman
A. Goerdt
Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations
322
12
M. Furer
On Interactive Proofs with a Laconic Prover
334
12
O. Goldreich
S. Vadhan
A. Wigderson
Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness
346
12
P. Hoyer
J. Neerbek
Y. Shi
Lower Bounds in the Quantum Cell Probe Model
358
12
P. Sen
S. Venkatesh
Concurrency
Axiomatizations for Probabilistic Bisimulation
370
12
E. Bandini
R. Segala
Noninterference for Concurrent Programs
382
14
G. Boudol
I. Castellani
Distributed Controller Synthesis for Local Specifications
396
12
P. Madhusudan
P.S. Thiagarajan
A Distributed Abstract Machine for Safe Ambients
408
13
D. Sangiorgi
A. Valente
Towards Quantitative Verification of Probabilistic Transition Systems
421
12
F. van Breugel
J. Worrell
Efficient Datastructures
Efficient Generation of Plane Triangulations without Repetitions
433
11
Z. Li
S-i. Nakano
The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations
444
12
G.-H. Lin
Z.-Z. Chen
T. Jiang
J. Wen
Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher
456
13
S.-M. Park
J.-H. Lee
K.-Y. Chwa
A New Method for Balancing Binary Search Trees
469
12
S. Roura
Graph Algorithms
Permutation Editing and Matching via Embeddings
481
12
G. Cormode
S. Muthukrishnan
S.C. Sahinalp
Testing Hypergraph Coloring
493
13
A. Czumaj
C. Sohler
Total Colorings of Degenerated Graphs
506
12
S. Isobe
X. Zhou
T. Nishizeki
Decidable Properties of Graphs of All-Optical Networks
518
12
L. Margara
J. Simon
Majority Consensus and the Local Majority Rule
530
13
N.H. Mustafa
A. Pekec
Language Theory, Codes and Automata
Solvability of Equations in Free Partially Commutative Groups Is Decidable
543
12
V. Diekert
A. Muscholl
Rational Transformations of Formal Power Series
555
12
M. Droste
G.-Q. Zhang
Combinatorics of Three-Interval Exchanges
567
12
S. Ferenczi
C. Holton
L.Q. Zamboni
Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages
579
12
T. Harju
O. Ibarra
J. Karhumaki
A. Salomaa
The Star Problem in Trace Monoids: Reductions Beyond C4
591
12
D. Kirsten
The Trace Coding Problem Is Undecidable
603
12
M. Kunc
Combinatorics of Periods in Strings
615
12
E. Rivals
S. Rahmann
Minimal Tail-Biting Trellises for Certain Cyclic Block Codes Are Easy to Construct
627
12
P. Shankar
P.N.A. Kumar
H. Singh
B.S. Rajan
Model Checking and Protocol Analysis
Effective Lossy Queue Languages
639
13
P.A. Abdulla
L. Boasson
A. Bouajjani
Model Checking of Unrestricted Hierarchical State Machines
652
15
M. Benedikt
P. Godefroid
T. Reps
Symbolic Trace Analysis of Cryptographic Protocols
667
15
M. Boreale
Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols
682
12
H. Comon
V. Cortier
J. Mitchell
Fair Simulation Relations, Parity Games, and State Space Reduction for Buchi Automata
694
14
K. Etessami
T. Wilke
R.A. Schuller
Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
708
12
G. Gottlob
R. Pichler
From Finite State Communication Protocols to High-Level Message Sequence Charts
720
12
A. Muscholl
D. Peled
Networks and Routing
Fractional Path Coloring with Applications to WDM Networks
732
12
I. Caragiannis
A. Ferreira
C. Kaklamanis
S. Perennes
H. Rivano
Performance Aspects of Distributed Caches Using TTL-Based Consistency
744
13
E. Cohen
E. Halperin
H. Kaplan
Routing in Trees
757
16
P. Fraigniaud
C. Gavoille
Online Packet Routing on Linear Arrays and Rings
773
12
J.T. Havill
Faster Gossiping on Butterflies
785
12
J.F. Sibeyn
Reasoning and Verification
Realizability and Verification of MSC Graphs
797
12
R. Alur
K. Etessami
M. Yannakakis
Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs
809
12
P. Madhusudan
A Set-Theoretic Framework for Assume-Guarantee Reasoning
821
14
P. Maier
Foundations for Circular Compositional Reasoning
835
13
M. Viswanathan
R. Viswanathan
Scheduling
A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines
848
14
C. Chekuri
S. Khanna
The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts
862
13
M. Chrobak
J. Csirik
C. Imreh
J. Noga
J. Sgall
G.J. Woeginger
On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates
875
12
A.V. Fishkin
K. Jansen
L. Porkolab
On the Approximability of Average Completion Time Scheduling under Precedence Constraints
887
11
G.J. Woeginger
Secure Computation
Optimistic Asynchronous Multi-party Contract Signing with Reduced Number of Rounds
898
14
B. Baum-Waidner
Information-Theoretic Private Information Retrieval: A Unified Construction
912
15
A. Beimel
Y. Ishai
Secure Multiparty Computation of Approximations
927
12
J. Feigenbaum
Y. Ishai
T. Malkin
K. Nissim
M.J. Strauss
R.N. Wright
Secure Games with Polynomial Expressions
939
12
A. Kiayias
M. Yung
Specification and Deduction
On the Completeness of Arbitrary Selection Strategies for Paramodulation
951
12
M. Bofill
G. Godoy
An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS
963
16
F. Honsell
M. Miculan
I. Scagnetto
Knuth-Bendix Constraint Solving Is NP-Complete
979
14
K. Korovin
A. Voronkov
Amalgamation in CASL via Enriched Signatures
993
12
L. Schroder
T. Mossakowski
A. Tarlecki
Structural Complexity
Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution
1005
12
A. Atserias
M.L. Bonet
J.L. Esteban
Time and Space Bounds for Reversible Simulation
1017
11
H. Buhrman
J. Tromp
P. Vitanyi
Finite-State Dimension
1028
12
J.J. Dai
J.I. Lathrop
J.H. Lutz
E. Mayordomo
The Complexity of Computing the Size of an Interval
1040
12
L.A. Hemaspaandra
S. Kosub
K.W. Wagner
Communication Gap for Finite Memory Devices
1052
13
T. Jurdzinski
M. Kutylowski
Separating Quantum and Classical Learning
1065
16
R.A. Servedio
Author Index
1081