Logical Approaches to Computational Barriers

Asymptotic Densities in Logic

Speaker:
| Marek Zaionc |

Slot: |
Array, 17:40-18:00, col. 4 |

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 |