Invited Lecture

• 
  Yonit Kesten, Amir Pnueli, Li-on Raviv: Algorithmic Verification of Linear Temporal Logic Specifications. 1-16

Complexity

• 
  Bernd Borchert, Dietrich Kuske, Frank Stephan: On Existentially First-Order Definable Languages and Their Relation to NP. 17-28
• 
  Jean-François Raymond, Pascal Tesson, Denis Thérien: An Algebraic Approach to Communication Complexity. 29-40

Verification

• 
  Rajeev Alur, Kenneth L. McMillan, Doron Peled: Deciding Global Partial-Order Properties. 41-52
• 
  Xinxin Liu, Scott A. Smolka: Simple Linear-Time Algorithms for Minimal Fixed Points (Extended Abstract). 53-66

Data Structures

• 
  Thore Husfeldt, Theis Rauhe: Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method. 67-78
• 
  Torben Hagerup: Simpler and Faster Dictionaries on the AC⁰ RAM. 79-90

Concurrency

• 
  Slawomir Lasota: Partial-Congruence Factorization of Bisimilarity Induced by Open Maps. 91-102
• 
  Catherine Dufourd, Alain Finkel, Ph. Schnoebelen: Reset Nets Between Decidability and Undecidability. 103-115

Invited Lecture

• 
  Mark H. Overmars: Geometric Algorithms for Robotic Manipulation. 116-117

Computational Geormetry

• 
  Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, Hsueh-I Lu: Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses. 118-129
• 
  Thorsten Graf, Kamakoti Veezhinathan: Reducing Simple Polygons to Triangles - A Proof for an Improved Conjecture. 130-139

Automata and Temporal Logic

• 
  Igor Walukiewicz: Difficult Configurations - On the Complexity of LTrL. 140-151
• 
  Bernard Boigelot, Stéphane Rassart, Pierre Wolper: On the Expressiveness of Real and Integer Arithmetic Automata (Extended Abstract). 152-163

Algorithms

• 
  David Peleg: Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees. 164-175
• 
  Magnús M. Halldórsson, Jan Kratochvíl, Jan Arne Telle: Independent Sets with Domination Constraints. 176-187

Infinite State Systems

• 
  Madhavan Mukund, K. Narayan Kumar, Jaikumar Radhakrishnan, Milind A. Sohoni: Robust Asynchronous Protocols Are Finite-State. 188-199
• 
  Petr Jancar, Antonín Kucera, Richard Mayr: Deciding Bisimulation-Like Equivalences with Finite-State Processes. 200-211

Invited Lecture

• 
  Avi Wigderson: Do Probabilistic Algorithms Outperform Deterministic Ones? 212-214

Complexity

• 
  Vince Grolmusz: A Degree-Decreasing Lemma for (MOD q - MOD p) Circuits. 215-222
• 
  Chi-Jen Lu: Improved Pseudorandom Generators for Combinatorial Rectangles. 223-234

Verification

• 
  Amir Pnueli, Ofer Strichman, Michael Siegel: Translation Validation for Synchronous Languages. 235-246
• 
  Vladimir A. Zakharov: An Efficient and Unified Approach to the Decidability of Equivalence of Propositional Programs. 247-258

Complexity

• 
  Stasys Jukna, Stanislav Zák: On Branching Programs With Bounded Uncertainty (Extended Abstract). 259-270
• 
  Amir M. Ben-Amram, Holger Petersen: CONS-Free Programs with Tree Input (Extended Abstract). 271-282

Concurrency

• 
  Paolo Baldan, Andrea Corradini, Ugo Montanari: Concatenable Graph Processes: Relating Processes and Derivation Traces. 283-295
• 
  Fabio Gadducci, Ugo Montanari: Axioms for Contextual Net Processes. 296-308

Invited Lecture

• 
  Andrew M. Pitts: Existential Types: Logical Relations and Operational Equivalence. 309-326

Algorithms

• 
  Conrado Martínez, Salvador Roura: Optimal Sampling Strategies in Quicksort. 327-338
• 
  Martin E. Dyer, Catherine S. Greenhill: A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables. 339-350

Semantics

• 
  John Power, Giuseppe Rosolini: A Modular Approach to Denotational Semantics. 351-362
• 
  Pasquale Malacaria, Chris Hankin: Generalised Flowcharts and Games. 363-374

Approximation

• 
  Ming-Yang Kao, Jie Wang: Efficient Minimization of Numerical Summation Errors. 375-386
• 
  Cristina Bazgan, Miklos Santha, Zsolt Tuza: Efficient Approximation Algorithms for the Subset-Sums Equality Problem. 387-396

Theorem Proving

• 
  Eduardo Giménez: Structural Recursive Definitions in Type Theory. 397-408
• 
  Denis Lugiez: A Good Class of Tree Automata and Application to Inductive Theorem Proving. 409-420

Formal Languages

• 
  Juhani Karhumäki, Arto Lepistö, Wojciech Plandowski: Locally Periodic Infinite Words and a Chaotic Behaviour. 421-430
• 
  Jean-Eric Pin: Bridges for Concatenation Hierarchies. 431-442

Pi-calculus

• 
  Huimin Lin: Complete Proof Systems for Observation Congruences in Finite-Control pi-Calculus. 443-454
• 
  Björn Victor, Joachim Parrow: Concurrent Constraints in the Fusion Calculus. 455-469

Automata and BSP

• 
  Michele d'Amico, Giovanni Manzini, Luciano Margara: On Computing the Entropy of Cellular Automata. 470-481
• 
  Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery Westbrook: On the Determinization of Weighted Finite Automata. 482-493
• 
  Alexandre Tiskin: Bulk-Synchronous Parallel Multiplication of Boolean Matrices. 494-506

Rewriting

• 
  Hélène Touzet: A Complex Example of a Simplifying Rewrite System. 507-517
• 
  Paul-André Melliès: On a Duality Between Kruskal and Dershowitz Theorems. 518-529
• 
  Daria Walukiewicz: A Total AC-Compatible Reduction Ordering on Higher-Order Terms. 530-542

Invited Lecture

• 
  Thomas A. Henzinger: Model Checking Game Properties of Multi-agent Systems (Abstract). 543

Networks and Routing

• 
  Luisa Gargano: Limited Wavelength Conversion in All-Optical Tree Networks. 544-555
• 
  Shiva Chaudhuri, K. V. Subrahmanyam, Frank Wagner, Christos D. Zaroliagis: Computing Mimicking Networks. 556-567

Real Time

• 
  Christel Baier, Joost-Pieter Katoen, Diego Latella: Metric Semantics for True Concurrent Real Time. 568-579
• 
  Thomas A. Henzinger, Jean-François Raskin, Pierre-Yves Schobbens: The Regular Real-Time Languages. 580-591

Networks and Routing

• 
  Serafino Cicerone, Gabriele Di Stefano, Michele Flammini: Static and Dynamic Low-Congested Interval Routing Schemes. 592-603
• 
  Doug Cook, Vance Faber, Madhav V. Marathe, Aravind Srinivasan, Yoram J. Sussmann: Low-Bandwidth Routing and Electrical Power Networks. 604-615

Automata and Temporal Logic

• 
  Fritz Henglein, Jakob Rehof: Constraint Automata and the Complexity of Recursive Subtype Entailment. 616-627
• 
  Moshe Y. Vardi: Reasoning about The Past with Two-Way Automata. 628-641

Invited Lecture

• 
  Leslie G. Valiant: A Neuroidal Architecture for Cognitive Computation. 642-669

Approximation

• 
  David Peleg, Eilon Reshef: Deterministic Polylog Approximation for Minimum Communication Spanning Trees. 670-681
• 
  Artur Czumaj, Andrzej Lingas: A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity. 682-694

Pi-calculus

• 
  Peter Sewell: Global/Local Subtyping and Capability Inference for a Distributed pi-calculus. 695-706
• 
  Zhoujun Li, Huowang Chen: Checking Strong/Weak Bisimulation Equivalences and Observation Congruence for the pi-Calculus. 707-718

Algorithms

• 
  Dario Bini, Gianna M. Del Corso, Giovanni Manzini, Luciano Margara: Inversion of Circulant Matrices over Z_m. 719-730
• 
  Wojciech Plandowski, Wojciech Rytter: Application of Lempel-Ziv Encodings to the Solution of Words Equations. 731-742

Theorem Proving

• 
  Neil Ghani, Valeria de Paiva, Eike Ritter: Explicit Substitutions for Constructive Necessity. 743-754
• 
  Gilles Barthe: The Relevance of Proof-Irrelevance. 755-768

Invited Lecture

• 
  Gilles Brassard: New Horizons in Quantum Information Processing. 769-771

Zero-Knowledge

• 
  Ivan Damgård, Birgit Pfitzmann: Sequential Iteration of Interactive Arguments and an Efficient Zero-Knowledge Argument for NP. 772-783
• 
  Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung: Image Density is Complete for Non-Interactive-SZK (Extended Abstract). 784-795

Semantics

• 
  Peter Hertling, Klaus Weihrauch: Randomness Spaces. 796-807
• 
  Antonio Bucciarelli, Ivano Salvo: Totality, Definability and Boolean Ciruits. 808-819

Quantum Computing and Computational Biology

• 
  Gilles Brassard, Peter Høyer, Alain Tapp: Quantum Counting. 820-831
• 
  Tatsuya Akutsu, Mutsunori Yagiura: On the Complexity of Deriving Score Functions from Examples for Problems in Molecular Biology. 832-843

Pi-calculus

• 
  Cédric Fournet, Georges Gonthier: A Hierarchy of Equivalences for Asynchronous Calculi. 844-855
• 
  Massimo Merro, Davide Sangiorgi: On Asynchrony in Name-Passing Calculi. 856-867

Invited Lecture

• 
  Martín Abadi: Protection in Programming-Language Translations. 868-883

Automata

• 
  Holger Petersen, John Michael Robson: Efficient Simulations by Queue Machines. 884-895
• 
  Pavol Duris, Tomasz Jurdzinski, Miroslaw Kutylowski, Krzysztof Lorys: Power of Cooperation and Multihead Finite Systems. 896-907

Programming Languages and Types

• 
  Olivier Danvy: A Simple Solution to Type Specialization. 908-917
• 
  Walid Taha, Zine-El-Abidine Benaissa, Tim Sheard: Multi-Stage Programming: Axiomatization and Type Safety. 918-929

last updated on Wed May 22 04:33:13 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page