BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

On Depth 1 Frege Systems Pudlak, Pavel


Combinatorial characterizations of canonical and interpolation pairs have been found for Frege system for every constant depth. The most interesting case is the canonical pair of Resolution which is equivalent to the interpolation pair of depth 1 Frege system. The first (formulation) is connected with weak automatibility of Resolution, the second with interpolation for the weakest fragment of Frege systems for which we do not have feasible interpolation. We will show several ways how these pairs can be presented and connections with monotone interpolation.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International