Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Asymptotic Densities in Logic


Speaker: Marek Zaionc
Slot: Array, 17:40-18:00, col. 4

Abstract

This talk presents numerous results from the area of quantitative
investigations in logic and type theory. For the given logical
calculus (or type theory) we investigate the proportion of the number
of distinguished formulas (or types) $A$ of a certain length $n$ to
the number of all formulas of such length. We are especially
interested in the asymptotic behavior of this fraction when $n$ tends to
infinity. The limit $\mu(A)$ if exists, is an asymptotic probability
of finding a formula from the class $A$ among all formulas, or the
asymptotic density of the set $A$. Often the set $A$ stands for all
tautologies of the given logical calculus (or all inhabited types in
type theory). In this case we call the asymptotic of $\mu(A)$ the
density of truth. Most of this research is concerned with classical
logic and sometimes with its intuitionistic fragments, but there are
also some attempts to examine modal logics. To do that we use methods
based on combinatorics, generating functions and analytic functions of
complex variables with special attention given to singularities
regarded as a key determinant to asymptotic behavior.


websites: Arnold Beckmann 2006-06-06