============================================================================================ The following papers (listed in random order) have been accepted at LICS 2006: ============================================================================================ Thierry Coquand and Arnaud Spiwack. Proof of strong normalisation using domain theory Emil Kiss and Matthew Valeriote. On tractability and congruence distributivity Ugo Dal Lago. Context Semantics, Linear Logic and Computational Complexity Sharon Shoham and Orna Grumberg. 3-Valued Abstraction: More Precision at Less Cost Dietrich Kuske and Markus Lohrey. Monadic chain logic over iterations and applications to pushdown systems Olivier Laurent and Lorenzo Tortora de Falco. Obsessional cliques: a semantic characterization of bounded time complexity Luke Ong. On model-checking trees generated by higher-order recursion schemes Lutz Schröder and Dirk Pattinson. PSPACE reasoning for coalgebraic modal logic Benoit Larose, Cynthia Loten and Claude Tardif. A Characterisation of First-Order Constraint Satisfaction Problems Giulio Manzonetto and Antonino Salibra. Boolean algebras for lambda calculus Guoqiang Pan and Moshe Vardi. Fixed-Parameter Hierarchies inside PSPACE Tachio Terauchi and Alex Aiken. On Typability for Rank-2 Intersection Types with Polymorphic Recursion Thomas Ball and Orna Kupferman. An Abstraction-Refinement Framework for Multi-Agent Systems Nir Piterman. From Nondeterministic Büchi and Streett Automata to Deterministic Parity Automata Mariangiola Dezani and Makoto Tatsuta. Normalisation is insensible to lambda-term identity or difference Tomas Brazdil, Vaclav Brozek, Vojtech Forejt and Antonin Kucera. Stochastic Games with Branching-Time Winning Objectives Marcelo Fiore and Sam Staton. A Congruence Rule Format for Name-Passing Process Calculi from Mathematical Structural Operational Semantics Martin Otto. The boundedness problem for monadic universal first-order logic Mikolaj Bojanczyk and Thomas Colcombet. Omega-Regular Expressions with Bounds Laura Chaubard, Jean-Eric Pin and Howard Straubing. First order formulas with modular predicates Nir Piterman and Amir Pnueli. Faster Solutions of Street and Rabin Games Daniel Leivant. Matching explicit and modal reasoning about programs: a proof theoretic delineation of dynamic logic Jonathan Hayman and Glynn Winskel. Independence and Concurrent Separation Logic Filippo Bonchi, Ugo Montanari and Barbara König. Saturated Semantics for Reactive Systems Mikolaj Bojanczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin and Claire David. Two-Variable Logic on Words with Data Orna Kupferman and Moshe Vardi. Memoryful Branching-Time Logic Patricia Bouyer, Thomas Brihaye and Fabrice Chevalier. Control in o-minimal hybrid systems Anuj Dawar, Martin Grohe, Stephan Kreutzer and Nicole Schweikardt. Approximation Schemes for First-Order Definable Optimization Problems Daniele Varacca and Hagen Voelzer. Temporal logics and model checking for fairly correct systems Matthew Parkinson, Richard Bornat and Cristiano Calcagno. Variables as Resource in Hoare Logics Vineet Kahlon and Aarti Gupta. An Automata-theoretic Appraoch for Model Checking Threads for LTL Properties Catuscia Palamidessi, Vijay Saraswat, Frank D. Valencia and Bjorn Victor. On the Expressiveness of Linearity vs Persistence in the Asynchronous Pi-Calculus Eldar Fischer, Frederic Magniez and Michel de Rougemont. Approximate Satisfiability and Equivalence Soren Lassen. Head normal form bisimulation for pairs and the lambda-mu calculus Dexter Kozen. Coinductive Proof Principles for Stochastic Processes Stephane Demri and Ranko Lazic. LTL with the Freeze Quantifier and Register Automata Alexis Maciel and Toniann Pitassi. A Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives Adam Barth and John C. Mitchell. Managing Digital Rights using Linear Logic Marcin Jurdzinski and Ashutosh Trivedi. Average Time Games
============================================================================================ The following short presentations (listed in random order) have been accepted at LICS 2006: ============================================================================================ Julian Zinn and Rakesh Verma. A Polynomial-time Algorithm for Uniqueness of Normal Forms of Linear Shallow Term Rewrite Systems Aaron Hunter. Non-Closure Results for First-Order Spectra Detlef Kaehler, Ralf Kuesters and Thomas Wilke. A Dolev-Yao-based Definition of Abuse-free Protocols Guillaume Burel and Claude Kirchner. An Abstract Completion Procedure for Cut Elimination in Deduction Modulo Roberto Maieli and Paul Ruet. Interactive correctness criterion for multiplicative-additive proof-nets Leona F. Fass. A Logical Look at Agents' Problem-Solving on the Semantic Web Jørgen Villadsen. Nominalization in Intensional Type Theory Murray Patterson, Yongmei Liu, Eugenia Ternovska and Arvind Gupta. Grounding for Model Expansion in k-Guarded Formulas