20. LICS 2005: Chicago, IL, USA

20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26-29 June 2005, Chicago, IL, USA, Proceedings. IEEE Computer Society 2005, ISBN 0-7695-2266-1 BibTeX

Front Cover.
Electronic Edition (link) BibTeX
Cover Pages.
Electronic Edition (link) BibTeX
Prakash Panangaden:
Foreword.
Electronic Edition (link) BibTeX
Conference Organization.
Electronic Edition (link) BibTeX
Program Committee.
Electronic Edition (link) BibTeX
Additional Reviewers.
Electronic Edition (link) BibTeX

Session 1

Glynn Winskel:
Relations in Concurrency. 2-11
Electronic Edition (link) BibTeX
Jos C. M. Baeten, Flavio Corradini:
Regular Expressions in Process Algebra. 12-19
Electronic Edition (link) BibTeX

Session 2

Anuj Dawar, Martin Otto:
Modal Characterisation Theorems over Special Classes of Frames. 21-30
Electronic Edition (link) BibTeX
Pablo Barceló, Leonid Libkin:
Temporal Logics over Unranked Trees. 31-40
Electronic Edition (link) BibTeX
Hannu Niemistö:
On Locality and Uniform Reduction. 41-50
Electronic Edition (link) BibTeX
Evan Goris, Maarten Marx:
Looping Caterpillars. 51-60
Electronic Edition (link) BibTeX

Session 3

Geoffrey Washburn, Stephanie Weirich:
Generalizing Parametricity Using Information-flow. 62-71
Electronic Edition (link) BibTeX
Masahito Hasegawa:
Relational Parametricity and Control. 72-81
Electronic Edition (link) BibTeX
Paul-André Melliès, Jerome Vouillon:
Recursive Polymorphic Types and Parametricity in an Operational Framework. 82-91
Electronic Edition (link) BibTeX
Giuseppe Castagna, Rocco De Nicola, Daniele Varacca:
Semantic Subtyping for the p-Calculus. 92-101
Electronic Edition (link) BibTeX

Session 5

Michael Benedikt:
An Insider's Guide to Logic in Telecommunications Data. 104-105
Electronic Edition (link) BibTeX
Albert Atserias:
On Digraph Coloring Problems and Treewidth Duality. 106-115
Electronic Edition (link) BibTeX

Session 6

Javier Esparza, Antonín Kucera, Richard Mayr:
Quantitative Analysis of Probabilistic Pushdown Automata: Expectations and Variances. 117-126
Electronic Edition (link) BibTeX
Parosh Aziz Abdulla, Noomene Ben Henda, Richard Mayr:
Verifying Infinite Markov Chains with a Finite Attractor or the Global Coarseness Property. 127-136
Electronic Edition (link) BibTeX
Christel Baier, Marcus Größer:
Recognizing omega-regular Languages with Probabilistic Automata. 137-146
Electronic Edition (link) BibTeX
Jérôme Leroux:
A Polynomial Time Presburger Criterion and Synthesis for Number Decision Diagrams. 147-156
Electronic Edition (link) BibTeX

Session 7

Patrice Godefroid, Michael Huth:
Model Checking Vs. Generalized Model Checking: Semantic Minimizations for Temporal Logics. 158-167
Electronic Edition (link) BibTeX
Markus Lohrey:
Model-Checking Hierarchical Structures. 168-177
Electronic Edition (link) BibTeX
Krishnendu Chatterjee, Thomas A. Henzinger, Marcin Jurdzinski:
Mean-Payoff Parity Games. 178-187
Electronic Edition (link) BibTeX
Joël Ouaknine, James Worrell:
On the Decidability of Metric Temporal Logic. 188-197
Electronic Edition (link) BibTeX

Session 8

Clemens Kupke, Yde Venema:
Closure Properties of Coalgebra Automata. 199-208
Electronic Edition (link) BibTeX
François Lamarche, Lutz Straßburger:
Constructing Free Boolean Categories. 209-218
Electronic Edition (link) BibTeX
Luigi Santocanale:
Completions of µ-algebras. 219-228
Electronic Edition (link) BibTeX
Martin Hofmann:
Proof-Theoretic Approach to Description-Logic. 229-237
Electronic Edition (link) BibTeX

Session 9

Jane Hillston:
Process Algebras for Quantitative Analysis. 239-248
Electronic Edition (link) BibTeX
Thorsten Altenkirch, Jonathan Grattage:
A Functional Quantum Programming Language. 249-258
Electronic Edition (link) BibTeX

Session 10

Lars Birkedal, Noah Torp-Smith, Hongseok Yang:
Semantics of Separation-Logic Typing and Higher-Order Frame Rules. 260-269
Electronic Edition (link) BibTeX
Kohei Honda, Nobuko Yoshida, Martin Berger:
An Observationally Complete Program Logic for Imperative Higher-Order Frame Rules. 270-279
Electronic Edition (link) BibTeX
Iovka Boneva, Jean-Marc Talbot, Sophie Tison:
Expressiveness of a Spatial Logic for Trees. 280-289
Electronic Edition (link) BibTeX
Chris Hardin:
Proof Theory for Kleene Algebra. 290-299
Electronic Edition (link) BibTeX

Session 11

Glynn Winskel:
Name Generation and Linearity. 301-310
Electronic Edition (link) BibTeX
Vladimiro Sassone, Pawel Sobocinski:
Reactive Systems over Cospans. 311-320
Electronic Edition (link) BibTeX
Bernd Finkbeiner, Sven Schewe:
Uniform Distributed Synthesis. 321-330
Electronic Edition (link) BibTeX
Bruno Blanchet, Martín Abadi, Cédric Fournet:
Automated Verification of Selected Equivalences for Security Protocols. 331-340
Electronic Edition (link) BibTeX

Session 12

Solomon Feferman:
Tarski's Influence on Computer Science. 342
Electronic Edition (link) BibTeX

Session 13

Walter Fontana:
Logic and Systems Biology. 344
Electronic Edition (link) BibTeX
Soren Lassen:
Eager Normal Form Bisimulation. 345-354
Electronic Edition (link) BibTeX

Session 14

Alexis Saurin:
Separation with Streams in the lambdaµ-calculus. 356-365
Electronic Edition (link) BibTeX
Ugo Dal Lago:
The Geometry of Linear Higher-Order Recursion. 366-375
Electronic Edition (link) BibTeX
Claudia Faggian, François Maurel:
Ludics Nets, a game Model of Concurrent Interaction. 376-385
Electronic Edition (link) BibTeX
Paul-André Melliès:
Asynchronous Games 4: A Fully Complete Model of Propositional Linear Logic. 386-395
Electronic Edition (link) BibTeX

Session 15

Michael J. Maher:
Herbrand Constraint Abduction. 397-406
Electronic Edition (link) BibTeX
Limin Jia, Frances Spalding, David Walker, Neal Glew:
Certifying Compilation for a Language with Stack Allocation. 407-416
Electronic Edition (link) BibTeX
Abbas Edalat, Dirk Pattinson:
Inverse and Implicit Functions in Domain Theory. 417-426
Electronic Edition (link) BibTeX
Martín Hötzel Escardó, Ho Weng Kin:
Operational Domain Theory and Topology of a Sequential Programming Language. 427-436
Electronic Edition (link) BibTeX

Session 16

Víctor Dalmau:
Generalized Majority-Minority Operations are Tractable. 438-447
Electronic Edition (link) BibTeX
Emanuel Kieronski, Martin Otto:
Small Substructures and Decidability Issues for First-Order Logic with Two Variables. 448-457
Electronic Edition (link) BibTeX
Albert Atserias:
Definability on a Random 3-CNF Formula. 458-466
Electronic Edition (link) BibTeX
Benjamin Rossman:
Existential Positive Types and Preservation under Homomorphisisms. 467-476
Electronic Edition (link) BibTeX