Friday 13th May, 12:15, room 310

posted 11 May 2016, 01:24 by Jakub Michaliszyn   [ updated 12 May 2016, 00:26 ]
Emanuel Kieroński

Uniform, one-dimensional fragment of first-order logic

Jednorodny, jednowymiarowy fragment logiki pierwszego rzędu,  UF1, został zaproponowany przez L. Hellę i A. Kuusisto jako rozszerzenie logiki z dwiema zmiennymi, FO2, w którym w nietrywialny sposób można używać relacji arności większej od 2.

Na seminarium podam definicję fragmentu UF1 (a także  wariantów pokrewnych), wspomnę o zdefiniowanych dla niego  grach w stylu Ehrenfeuchta  oraz przedstwię wyniki dotyczące rozstrzygalności i złożoności problemu spełnialności dla UF1 i jego rozszerzeń.
Comments