Paul-André Melliès (auth.), Zoltán Ésik (eds.)3540454586, 9783540454588
The 37 revised full papers presented together with 4 invited contributions were carefully reviewed and selected from 132 submissions. All current aspects of logic in computer science are addressed, including automated deduction and interactive theorem proving, constructive mathematics and type theory, equational logic and term rewriting, automata and formal logics, modal and temporal logic, model checking, logical aspects of computational complexity, finite model theory, computational proof theory, logic programming and constraints, lambda calculus and combinatory logic, categorical logic and topological semantics, domain theory, database theory, specification, extraction and transformation of programs, logical foundations of programming paradigms, verification of security protocols, linear logic, higher-order logic, nonmonotonic reasoning, as well as logics and type systems for biology.
Table of contents :
Front Matter….Pages –
Functorial Boxes in String Diagrams….Pages 1-30
Some Results on a Game-Semantic Approach to Verifying Finitely-Presentable Infinite Structures (Extended Abstract)….Pages 31-40
Automata and Logics for Words and Trees over an Infinite Alphabet….Pages 41-57
Nonmonotonic Logics and Their Algebraic Foundations….Pages 58-71
Semi-continuous Sized Types and Termination….Pages 72-88
Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation….Pages 89-103
A Finite Semantics of Simply-Typed Lambda Terms for Infinite Runs of Automata….Pages 104-118
The Power of Linear Functions….Pages 119-134
Logical Omniscience Via Proof Complexity….Pages 135-149
Verification of Ptime Reducibility for System F Terms Via Dual Light Affine Logic….Pages 150-166
MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay….Pages 167-181
Abstracting Allocation….Pages 182-196
Collapsibility in Infinite-Domain Quantified Constraint Satisfaction….Pages 197-211
Towards an Implicit Characterization of NC k ….Pages 212-224
On Rational Trees….Pages 225-239
Reasoning About States of Probabilistic Sequential Programs….Pages 240-255
Concurrent Games with Tail Objectives….Pages 256-270
Nash Equilibrium for Upward-Closed Objectives….Pages 271-286
Algorithms for Omega-Regular Games with Imperfect Information….Pages 287-302
Relating Two Standard Notions of Secrecy….Pages 303-318
Jump from Parallel to Sequential Proofs: Multiplicatives….Pages 319-333
First-Order Queries over One Unary Function….Pages 334-348
Infinite State Model-Checking of Propositional Dynamic Logics….Pages 349-364
Weak Bisimulation Approximants….Pages 365-379
Complete Problems for Higher Order Logics….Pages 380-394
Solving Games Without Determinization….Pages 395-410
Game Quantification on Automatic Structures and Hierarchical Model Checking Games….Pages 411-425
An Algebraic Point of View on the Crane Beach Property….Pages 426-440
A Sequent Calculus for Type Theory….Pages 441-455
Universality Results for Models in Locally Boolean Domains….Pages 456-470
Universal Structures and the Logic of Forbidden Patterns….Pages 471-485
On the Expressive Power of Graph Logic….Pages 486-500
Hoare Logic in the Abstract….Pages 501-515
Normalization of IZF with Replacement….Pages 516-530
Acyclicity and Coherence in Multiplicative Exponential Linear Logic….Pages 531-545
Church Synthesis Problem with Parameters….Pages 546-561
Decidable Theories of the Ordering of Natural Numbers with Unary Predicates….Pages 562-574
Separation Logic for Higher-Order Store….Pages 575-590
Satisfiability and Finite Model Property for the Alternating-Time μ -Calculus….Pages 591-605
Space-Efficient Computation by Interaction….Pages 606-621
The Ackermann Award 2006….Pages 622-626
Back Matter….Pages –
Reviews
There are no reviews yet.