slideshow 3

Logic seminar

usually takes place each Monday at 13:30 temporarily on Zoom starting at 15:30, normally in IM, rear building, ground floor
Chair: Pavel Pudlak, Neil Thapen, Jan Krajíček
More information on the old seminar web page. The programme is announced via the mailing list.

On the Parameterized Complexity of Equational Logic

Mateus de Oliveira Oliveira
Institute of Mathematics ASCR
Monday, 1. December 2014 - 13:30
In this work we study the validity problem in equational logic under the perspective of parameterized complexity theory. First we introduce a variant of equational logic in which sentences are pairs of the form $(t_1=t_2,omega)$ where $omega$ is an arbitrary ordering of the positions corresponding to subterms of $t_1$ and $t_2$. We call such pairs {em ordered equations}. To each ordered equation one may naturally associate a notion of width and to each proof of validity of an ordered equation one may naturally associate a notion of depth. We define the width of such a proof to be the maximum width of an ordered equation occurring in it. Finally, we introduce a parameter $b$ which restricts the way in which variables are substituted for terms. We say that a proof is $b$-bounded if all substitutions used in it satisfy such restriction. In a surprising result, we show that one may determine whether an ordered equation $(t_1=t_2,omega)$ has a $b$-bounded proof of width $c$ and depth $d$... more

Definability in (discretely) ordered integrally divisible modules

Petr Glivicky
Monday, 24. November 2014 - 13:30
An ordered R-module M with a distinguished element 1 > 0 is called integrally divisible if for each scalar 0 < r in R, any m from M can be divided by r with a remainder (i.e. m = rn + i for some n, i from M with 0 <= i < r1). I show that all definable sets in such a module M are "protoperiodic" and therefore M satisfies quantifier elimination up to bounded formulas. This result is particularly interesting if understood in a wider context of model theory of linear arithmetics. I will try to give a brief survey of this arithmetical background.

Definability in (discretely) ordered integrally divisible modules

Petr Glivický
Institute of Mathematics
Monday, 10. November 2014 - 13:30
An ordered R-module M with a distinguished element 1 > 0 is called integrally divisible if for each scalar 0 < r in R, any m from M can be divided by r with a remainder (i.e. m = rn + i for some n, i from M with 0 <= i < r1). I show that all definable sets in such a module M are "protoperiodic" and therefore M satisfies quantifier elimination up to bounded formulas. This result is particularly interesting if understood in a wider context of model theory of linear arithmetics. I will try to give a brief survey of this arithmetical background.

The PCP theorem in Bounded Arithmetics, Part 2

Ján Pich
Charles University
Monday, 28. April 2014 - 13:30
We will prove the exponential PCP theorem in the theory APC_1, the PCP theorem in PV_1, assuming certain facts about (n,d,lambda)-graphs, and will discuss the possibility of deriving the PCP theorem in S^1_2 unconditionally.

Pages