Front matter
1-10
Model Checking: Theory into Practice
E. Allen Emerson
11-45
An Algebra for XML Query
Mary Fernandez, Jerome Simeon and Philip Wadler
46-54
Irregularities of Distribution, Derandomization, and Complexity Theory
Bernard Chazelle
55-80
Rewriting Logic as a Metalogical Framework
David Basin, Manuel Clavel and José Meseguer
81-86
Frequency Assignment in Mobile Phone Systems
Martin Grötschel
87-93
Data Provenance: Some Basic Issues
Peter Buneman, Sanjeev Khanna and Wang-Chiew Tan
94-105
Fast On-Line/Off-Line Algorithms for Optimal Reinforcement of a Network and Its Connections with Principal Partition
Sachin B. Patkar and H. Narayanan
106-116
On-Line Edge-Coloring with a Fixed Number of Colors
Lene Monrad Favrholdt and Morten Nyhave Nielsen
117-126
On Approximability of the Independent/Connected Edge Dominating Set Problems
Toshihiro Fujito
127-138
Model Checking CTL Properties of Pushdown Systems
Igor Walukiewicz
139-150
A Decidable Dense Branching-Time Temporal Logic
Salvatore La Torre and Margherita Napoli
151-163
Fair Equivalence Relations
Orna Kupferman, Nir Piterman and Moshe Y. Vardi
164-175
Arithmetic Circuits and Polynomial Replacement Systems
Pierre McKenzie, Heribert Vollmer and Klaus W. Wagner
176-187
Depth-3 Arithmetic Circuits for
S
innsu2
(X) and Extensions of the Graham-Pollack Theorem
Jaikumar Radhakrishnan, Pranab Sen and Sundar Vishwanathan
188-200
The Bounded Weak Monadic Quantifier Alternation Hierarchy of Equational Graphs Is Infinite
Olivier Ly
201-213
Combining Semantics with Non-standard Interpreter Hierarchies
Sergei Abramov and Robert Glück
214-226
Using Modes to Ensure Subject Reduction for Typed Logic Programs with Subtyping
Jan-Georg Smaus, François Fages and Pierre Deransart
227-239
Dynamically Ordered Probabilistic Choice Logic Programming
Marina De Vos and Dirk Vermeir
240-251
Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems
R. Fellows Michael, Catherine McCartin, A. Rosamond Frances and Ulrike Stege
252-263
Planar Graph Blocking for External Searching
Surender Baswana and Sandeep Sen
264-276
A Complete Fragment of Higher-Order Duration μ-Calculus
Dimitar P. Guelev
277-289
A Complete Axiomatisation for Timed Automata
Huimin Lin and Wang Yi
290-301
Text Sparsification via Local Maxima
Extended Abstract
Pilu Crescenzi, Alberto Del Lungo, Roberto Grossi, Elena Lodi and Linda Pagli, et al.
302-311
Approximate Swapped Matching
Amihood Amir, Moshe Lewenstein and Ely Porat
312-324
A Semantic Theory for Heterogeneous System Design
Rance Cleaveland and Gerald Lüttgen
325-335
Formal Verification of the Ricart-Agrawala Algorithm
Ekaterina Sedletsky, Amir Pnueli and Mordechai Ben-Ari
336-347
On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation
Johannes Köbler and Wolfgang Lindner
348-360
Θ
in2sup
-Completeness: A Classical Approach for New Results
Holger Spakowski and Jörg Vogel
361-372
Is the Standard Proof System for SAT P-Optimal?
Extended Abstract
Johannes Köbler and Jochen Messner
373-384
A General Framework for Types in Graph Rewriting
Barbara König
385-396
The Ground Congruence for Chi Calculus
Yuxi Fu and Zhenrong Yang
397-408
Inheritance in the Join Calculus
Extended Abstract
Cédric Fournet, Cosimo Laneve, Luc Maranget and Didier Rémy
409-420
Approximation Algorithms for Bandwidth and Storage Allocation Problems under Real Time Constraints
Stefano Leonardi, Alberto Marchetti-Spaccamela and Andrea Vitaletti
421-428
Dynamic Spectrum Allocation: The Impotency of Duration Notification
Bala Kalyanasundaram and Kirk Pruhs
429-441
The Fine Structure of Game Lambda Models
Pietro Di Gianantonio and Gianluca Franco
442-453
Strong Normalization of Second Order Symmetric λ-Calculus
Michel Parigot
454-464
Scheduling to Minimize the Average Completion Time of Dedicated Tasks
Foto Afrati, Evripidis Bampis, Aleksei V. Fishkin, Klaus Jansen and Claire Kenyon
465-476
Hunting for Functionally Analogous Genes
Michael T. Hallett and Jens Lagergren
477-488
Keeping Track of the Latest Gossip in Shared Memory Systems
Bharat Adsul, Aranyak Mehta and Milind Sohoni
489-502
Concurrent Knowledge and Logical Clock Abstractions
Ajay D. Kshemkalyani
503-515
Decidable Hierarchies of Starfree Languages
Christian Gla\er and Heinz Schmitz
516-529
Prefix Languages of Church-Rosser Languages
Jens R. Woinowski
Back matter