Computer science logic
- 520pagine
- 19 ore di lettura
The content includes invited lectures and regular papers addressing various topics in complexity, logic, and verification. It discusses average-case complexity for random 3-SAT and explores abstract interpretations of proofs in classical propositional calculus. Applications of Craig interpolation to model checking are examined, alongside concepts of bindings and mobility in relation to the ?-quantifier. Key themes include Nash equilibria in stochastic games, bounding quantifiers, and exploration games on infinite graphs. The integration of equational reasoning into theorem proving is highlighted, as well as goal-directed methods for Łukasiewicz logic. A general theorem on termination of rewriting and predicate transformers in linear logic are also presented. The work delves into proof nets for multiplicative linear logic with units and the boundary between decidability and undecidability in transitive-closure logics. Further discussions cover game-based notions of locality, fixed points of type constructors, and higher-order matching in the linear ?-calculus. The exploration of dependent type theory with names and binding leads to advancements in mechanized program verification and functional scenarios for bytecode verification. Additional topics include intuitionistic LTL, parameterized model checking, bounded arithmetic theories, logical characterizations of PSPACE, and soundness issues in theorem proving. The collection
